In 2000 I spent three weeks in Europe.
Plane ticket: outbound Toronto to Helsinki, return London to Toronto: CAD 1160.
Three-week Eurail pass (the cheapest ‘full-service’ one): CAD 870.
I mostly stayed at youth hostels, which worked out to about CAD 30 - 40 per night (more expensive in England (L24.95/night in London (=CAD 65–yike!))).
I was at a conference in Helsinki for the first week, and food was included in the price of the conference (under 200 euros–extremely reasonable, considering it was Finland and all, almost as expensive as England).
I probbably spent another 1000 dollars on souvenirs, food, local bus passes, tickets to attractions, a ticket on the ship between Helsinki and Stockholm, a ticket on the Channel Tunnel train, etc. The rail pass gave me big discounts on some of these. I also spent two nights on a sleeper train, which eliminated the necessity of finding a hostel those nights.
So, all told, somewhere around CAD 3000 in total–I’m not sure of the exact amount.
Definitely do the youth hostel thing. Not only is it a lot cheaper than hotels, most hostels offer kitchen facilities so that you can buy food at local stores and prepare it yourself, rather than go to restaurants. This is a BIG money saver.
For the next step in saving money, join a "hospitality exchange’. This is a service where people give you a basic place to sleep for free. I’m a member of Pasporta Servo (PS), a service for Esperanto speakers. There are others.
When you join PS, you get a book listing hosts in various cities around the world. Various contact details are given. If you are going to a city with a host, you can call ahead; perhaps there will be a vacancy. I stayed in Copenhagen for three nights at no cost. 
The next step in saving monty is, of course, camping. And then staying with friends. On my trip, I didn’t want to lug additional camping hear around, so I ddn’t camp. And I didn’t know anyone over there, so staying with friends was out.