Airbnb, Wimdu, OneFineStay, and home-exchange sites. Assuming you're not traveling during the peak season, you can contact several owners on VRBO and see if they're willing to do a last second discount—you may get a great deal. In general, Northern Europe is more technologically developed than Southern Europe. For example, accommodations in Estonia, Germany, the UK are usually wired (and have websites), while Italy, Greece, and Bulgaria are still crawling into the 21st century.
Hostels: Hostelworld and Hostelbookers are a good resources. You'll usually share a bathroom and room with strangers. Although most people are in their 20s, senior citizens stay there. It's great for solo travels.
Overnight trains: There are transportation costs you have to pay anyway to get from point A to point B. Usually, for far less than the price of a hotel, you can get a bed in an overnight train. It not only saves you money, but also saves you time. The ultra frugal will opt for an overnight bus, which is the cheapest (and least comfortable) way to travel.
Couchsurfing: Stay with a local. Although you don't exchange money, you ought to do something nice, as I discuss in How To Be a Good Couchsurfing Guest. Servas also is somewhat popular in Europe.
Invisible camping: Thru-hikers call it stealth camping. You can call it urban camping. Whatever you call it, it involves discreetly camping in a city park (or anywhere near civilization). Do not set up before dusk (otherwise you'll attract unwanted attention). Vacate the area at sunrise and leave no trace, or else you risk angering the locals (or getting mugged).
Too often people don't travel because they think they can't afford it. Lodging is a big percentage of the cost of travel, so consider these many ways to lessen the bite. By renting from locals, couchsurfing, and doing some invisible camping, I was able to travel for three years in Eastern Europe.