The site Madridman.com has a lot of recommendations for relatively cheap hostals (not hostels). I ended up staying at a hotel, but Hostal Marlasca looks cheap and well-located.