I just got back from Madrid and had an awesome time--I miss it so much already! I went with two friends and we absolutely LOVED our hostal in Madrid. It's called Hostal Luz and it's in a great location--just off Calle Arenal, near Plaza Isabel II and the Opera metro stop, only a few blocks from Puerta del Sol, too. It is super clean and the lady who owns it is really nice. They have the same prices all year long (instead of raising prices in high tourist seasons) and we thought it was pretty cheap--we paid 18 Euros each per night for our airconditioned triple with TV. Here's the info: Hostal Luz, Calle Fuentes, 10. Telf: 91 542 07 59 or 91 559 74 18
Good luck and I hope you have a great time in Spain!!