affordable hotels in Madrid, Barcelona and Sevilla...

In Madrid, look for the Hostal Cruz Sol and the Hostal Santa Cruz, two newly modernized two-star hotels on Plaza Santa Cruz. Push their names together and add .com for the websites. ABout 50 Euro/night double. They're in the same building, steps from Plaza Mayor and two short blocks from Sol. See it below with Street View....
View Larger Map

I suggest you look at a map of Spain. Your itinerary makes no sense: note that Barcelona is way over in the NE corner of the country, while all your other stops are (more or less) clustered in the south central/southwest part of the country. Barcelona is a long way from everyplace else that you're going, so it should be the first or last place you go to on the trip.

Going Madrid -> Barcelona -> Granada -> Seville makes about as much sense as starting a trip Las Vegas then going to New York -> Tucson -> Phoenix.

Unless you're looking for a way to waste time and money, do all the cities that are geographically near each other (speaking regionally), then go all the way to Barcelona (or vice-versa). There's no sense in doubling back across the bulk of Spain - fly in on one end, fly out of the other.

Hope that helps.

If you plan to visit all those cities, your loop is do-able, but it'll be rushed. And if you're on a shoestring budget, you'll have trouble making the transportation runs if you're travelling in only a month's time. Walkup train fares Madrid-Barcelona can range as high as 129 Euro pp. You may be able to find some Estrella fares as low as 65 Euro, or Web fares as low as 44 Euro. Sevilla-Madrid are almost as expensive. Go to the Spanish rail website RENFE ASAP to see if there are any discount tickets left.
Another option is bus....a loooong haul from Madrid-Barcelona, and even longer back to Granada. You can check bus schedules and fares here. There are two overnight buses on Madrid-Barcelona, about 8 hours at 28 Euro pp.
For Madrid-Granada, see if there are any discount airfares left on your travel date. Vueling might still have some early morning mid-week flights from about 25 Euro pp (an extra 10 Euro per suitcased checked). Ryanair flies Barcelona "Girona" to Granada for about 40 Euro, all in....but you'll have to spend another 10-15 Euro on a bus from Barcelona to Girona airport.
Personally, if I had 12 days for a trip like this, I'd leave Barcelona for another visit...you'll have lots to keep you busy for 12 days in the Madrid-Granada-Sevilla triangle...and you may be able to include a visit to Cordoba.

Keep in mind that what we might normally call a hostel in other parts of Europe (college students, backpackers, shared baths, etc.) are not the same as hostals in Spain. Hostals in Spain are lovely, quaint, mostly privately owned and GREAT places to stay.

We stayed here in Madrid: Hostal Triana, @ Calle de la Salud 13. It is in Rick's book. It's nothing fancy, but clean and well located.

In Granada we stayed at: Hotel Anacapri @ Calle Joaquin Costa 7. Again, this is in Rick's book and was our favorite lodging of our Spain trip. If you show your RS book, you get breakfast free, which is a great deal. It's a very hearty breakfast.

In Seville we stayed at: Hotel Alcantara @ C/ Ximenez de Enciso 28. It's in Rick's book, too. Nice place. Great Flamenco show next door.

ENJOY!

Okay, we'll stick to Madrid and Barcelona. Any affordable places to stay? Thank you.

We stayed at the Pension Retiro in Madrid (http://pensionretiro.iespana.es/) Senora Antonia, while she doesn't speak much English, was an amazing hostess and just a wonderful woman. The rooms are located on a small street just across from the Prado. Also, just steps away are two great little cafes that look directly out at the Prado. You're also just about a block away from Retiro Park, which is a great place to walk through and enjoy your time in Madrid.