What exactly are paradors? How are they different/similar to hotels and hostals in regards to the rooms or ammenities? How do costs compare?

I had such a great time in May that I am already working on ideas for the trip next year!

Paradores are generally very nice places to stay with a high level of care and service . Typically they are very beautiful old buildings .. castles , mansions ,Old vineyard houses . Expect to pay quite a lot of money . They are popular with Spanish people but normally those Spanish that have money or those that are celebrating a special occasion . My local travel agent in Madrid has booklets about these very beautiful paradores .

http://www.paradores.es/en/portal.do

I have stayed in Paradores many, many time and really didn't find them very expensive, it has been several years, but from what I can remember we didn't spend much more than 85 euros per night...They have always been wonderful places and great food of the region served. My favorite was in Cuenca, if I remember correctly, it was so long ago, and a charming city to explore too.