Many cities are quite compact and can be seen by walking. Within a city centre transport or driving can be a hassle, and with a little more time you can get a much better feel for the area you are in.
Cycling is can be a good and cheap way to explore areas a little further apart than what you can see by walking. Some cities have cheap bicyle hire schemes run by urban governments. Check this out before you go, as some need advance registration.
However, in some countries like the USA or Australia, bicycle hire for two people can easily cost more than a car hire for the same period, and the market for second hand bicycles can take time to sell into. For an extended trip it will be much cheaper to buy a used bike rather than rent. Used bikes can usually be purchased for reasonable prices at thrift shops, pawn shops, and garage sales. They can sometimes be scavenged for free off the street when abandoned by others.
Also, travel insurance which usually covers rental car damage or excess payable usually does not cover loss or damage to a bicycle you may hire.
This can be combined with hitchhiking, which is faster and normally just as cheap.
By public transport
Use mass public transport instead of taxis or other faster, more expensive means of transportation, some cities even offer some forms of free transport in city centres.
However, in some places, it can be cheaper for three or four people to share a taxi than to take public transport. Shop around and compare.
For public transport, look into multi-use tickets. Many systems have tickets that can be used a certain number of times, or over a certain time period, for a considerable discount over buying each ticket individually.
Even national and international rail and bus networks may have discount tickets for a month's or several months' travel. You should also check what discounts you're eligible for: Western Europe frequently has blanket discount schemes for people under 26, Great Britain has a youth discount card that you can buy and which pays for itself after three or four journeys (a 'Young Person's Rail Card'), and many countries have discount schemes for students, pensioners and sometimes disabled people.
Local transport is often considerably cheaper than express or long distance transport. In European countries in the outskirts of a cities public transport system can often overlap with a neighbouring city, often providing a cheaper method of transport than an inter-city trip. In countries like Japan, local trains are cheaper if you have time on your hands and can manage the connections.
In Germany you can try to hitchhike on trains with people carrying Schoenes Wochenende tickets on the weekends.
In many parts of the world, especially Europe, it is possible to save money on travel by "ride sharing". There are websites where people post their travel details: where, when, what kind of car they have, how many spare seats, and how much they want you to pay them. It's not just a great way to cut travel costs, it can also be a great way to meet new people! In Germany, this kind of travel is called a "Mitfahrgelegenheit".
In the United States, you can try a driveaway car service. In this service, you pay a small fee to an agency to deliver a car to a business or individual in another city, often hundreds or thousands of miles away. The customer wins by reducing his shipping costs, and you win by having a car to drive for cheap. You are often allowed a certain amount of flexibility in the route and delivery time, allowing you freedom to explore. This is also possible, although not very common in Canada. HitTheRoad.ca is a Canada based Driveaway Service.
Camping is an obvious choice for cheap accommodation, and it's often the closest accommodation to lots of natural attractions. This will mean burdening yourself with whatever camping equipment is necessary to protect you from the weather at your destination. Also, many popular sites like national parks limit camping to particular spots and have you pay for a site. This is almost always cheaper than hostels except in very very popular camping spots.
You could sleep rough, that is sleep out of doors wherever you find a spot. This is difficult for three reasons: the first is that it will often get you in trouble with the police if you do it in urban areas; the second is that it makes you unusually vulnerable to crime, both theft and violence; and the third is weather. There are few places where this is seen as an acceptable way to holiday (ie "sorry officer I'm on holidays" is unlikely to be believed): however Sweden, Norway and Finland has the Right to access principle allowing you to camp on most private property, and in Japan you can participate in the nojuku tradition. The real key to sleeping rough is to arrive late in the evening and pack up early in the morning. Also look for areas with rugged topography and thick vegetation that will interrupt the line of sight and ease concealment. Also consider using a tent or hammock that blends well with area vegetation, green is best for most areas.
You could sleep in your car. Although also illegal in many areas, if you have a van style vehicle with limited rear windows, it is often easy to get away with.
The objective of hospitality exchange networks is to meet new, and local, people. It can be a great way to get a free place to stay the night, but besides that it's a fun and easy way to get acquainted with an area, city or culture. Active users of online hospitality exchange networks also tend to have broadband connections, which you can use while you are staying there.
You can stay in hostels or guesthouses, usually the cheapest type of commercial tourist accommodation. Many hostels offer cheap one- to four-person rooms, but the cheapest of all are dorms shared by up to twenty people: you'll usually be given a key to the room and left to choose a bunk bed. There are some international hostel associations, members of which get discounts at participating hostels. Bring a sleep sheet (two sheets sewn together like a sleeping bag) so you will not have to rent linen at hostels. Dorms are a great way to meet fellow travellers.
If you have a long distance train or bus pass, you can often sleep on a train or bus.
The cheapest places to buy food are traditional markets, supermarkets and street vendors. In countries with peculiarly high hygiene standards, you may be able to find perfectly acceptable food in supermarket's rubbish (note that taking that food might be considered stealing in certain jurisdictions).
In some cities there are very cheap restaurants in squats, usually selling vegetarian or vegan food for the price of the ingredients; for example Germany's Volksküchen. Some countries also have heavily subsidised university restaurants sometimes open to foreign students as well. Germany for instance has Mensas, offering famously tasteless small-sized meals for 2-3 € (for non-students a substantially higher price may be charged, making the fast food chains cheaper); in large cities, there are also restaurants run by immigrants offering food for 4-6 €; restaurants offering German cuisine tend to be cheaper in districts with a high unemployment rate and in rural areas.
Self catering, buying your own ingredients and preparing your own meals, is a great way to stay on a budget. Many hostels provide kitchens where you can cook your meals.
For restaurants, avoid eating in the main tourist thoroughfares. If you get into the side streets and back alleys, you'll find cheaper restaurants that often serve tastier, more authentic meals.
See and Do
Many art galleries, museums and other attractions are free. Of those that require an entry fee, some have discounted or free days at least once a month, or a time after which admission is discounted or free.
Tourist information offices will sometimes be able to tell you about these.
The most straightforward way to earn money on the road is obviously to find some work. This is more easily done through contacts, and as a matter of fact hitchhiking may come very handy here. Contacting expatriates may also provide opportunities.
Obvious jobs for travellers include harvesting, Teaching English and waiting at restaurants or bars in tourist areas.
Wwoofing is a term for working 5 hours or so a day in exchange for lodging and food: it stands for World-Wide Opportunities on Organic Farms. See wwoof.org.
Resources exist, such as Susan Griffith's biennial Work your Way around the World published by Vacation Work.
In many places in Western Europe, and possibly also in other parts of the world, you can find give-away shops, shops where you can take things you want for free (as long as you don't take too much), and where you can leave stuff you don't need anymore.
It is really good to combine this with dumpster diving, looking for usable stuff at the garbage - you can bring the usable things you find there and don't want to have yourself to the give-away shops!
BookCrossing is a book exchange network. Books are travelling through the world, looking for people to read them! You might have encountered books with BookCrossing stickers already, but on the website you can look for places to find them.
Buy your air tickets only in sales. Low cost airlines sometimes offer air tickets for very little prices. Register for their newsletters or try MyAirDeals that alerts you on air ticket sales on your routes. With a bit of luck you can fly even below the price of airport taxes and charges.
To really stretch your budget, here are some money-saving tips:
In places where drinking bottled water is necessary, buy the biggest bottle of drinking water you can find in the local supermarket. Leave it at your place of accommodation, and use it to refill a smaller bottle you carry around with you. That way you can save through bulk purchase and reduce waste. Or boil your water and use it to refill bottles.
Travel slowly. Staying in the same location several weeks or months reduces transportation costs and gives you time to determine the cheapest places to stay (you can usually negotiate lower rates for extended stays), eat and visit. Rushing around compounds costs.
Join a group tour - often there are significant group discounts and you can visit places that would be far more expensive if you visited on your own.