I stayed at Residencial Luz (32.50 euros for a double ensuite) in Tomar on Tuesday and can advise that it's cheap, relatively clean, and very centrally located. It's not the best property of its type in which I've stayed in Portugal, but it does the job and you can ask for (and get) rooms that essentially front on the Praca da Republica and, if you turn your head, you get a wonderful view of the Convento de Cristo ramparts from your room. Tomar is a lovely town, and markedly absent of tourists at this time of year (I counted 20 the entire time we were at the Convento de Cristo, and almost all of them seemed to be Portuguese), and well worth the detour.
I found out too late that train fare to Tomar and admission to the Convento is covered by the Lisboa Card -- as are the UNESCO sites in Batalha and Alcobaca, as well as comboio trips to Sintra and Cascais -- so you might just want to think about getting a cheap room in Lisbon for four or five days and making day trips to the surrounding region, with one overnight at Tomar. If I had to do my recent trip over again, and wanted to do it cheaply, I'd have done this:
Day 1: Lisbon. Buy the Lisbon Card for three days (approx 30 Euros/person for three days) and spend an hour or two at the Castelo de Sao Jorge if you haven't seen it before. Head off to Tomar by train and tour the Convento. Overnight in Tomar. You can try to work in a quick sidetrip to Alcobaca or Batalha (there's about four or five buses a day on the Nazare-Batalha-Alcobaca-Tomar route @ 8.6 Euros a person), but that would make for a very long day.
Day 2: Take the train from Tomar to Santa Appollonia station, the metro from SA to Restauradores station, and then the Sintra interurban train to Sintra. That's three hours of travelling right there, but you'll then have the day in Sintra. After touring Sintra, return in the evening and crash in a cheap room in Lisbon. All transit costs are again covered by the Lisbon Card.
Day 3: Tour the Alfama district in the morning, Belem in the afternoon, and, if you're up to it, have dinner in Cascais. All transit is, again, covered by the Lisbon Card.
I found the Lisbon Card to be a good deal, but you have to remember to keep the accompanying book with you, as many attractions will demand the coupons in the book before they will give you the promised discount. I'd also suggest that the 2006 LP book "Best of Lisbon" is already out of date and contains some misinformation (Sintra trains leave from Rossio, not Entrecampos!), so be wary of it.
Finally, no one advertised cheap rooms at the various bus and train stations that I visited in the same way that one would be able to get a casa particular in Cuba by just showing up. I was, however, handed an ad for what looked like a cheap residencial in Lisbon while waiting around for a train at Santa Appolonia station. I already had a room, so didn't investigate further.
Have fun! Although I just returned from Portugal myself, I'd go back again in a heartbeat.