These are all great suggestions! Most of them I've never even considered. My travel experiences are a bit different as my work requires substantial travel. So far I have seen 25 different countries and 30 states for work . I've also done a ton of personal travelling, but pre-moustachian phase so I wasn't as frugal as I am now. Some of these will apply to folks who travel a lot, others will not. Apologies in advance, this is a topic that I am personally quite passionate about!
1. If you do travel for work, always maximize points opportunities regardless of the airline / hotel program. Sign-up for everything and then convert right away if you need to. Most will offer conversion programs later which although a rip-off, allow you to now miss out on any opportunity.
2. If you have hotel status, try and stay at those hotels when possible. They typically have breakfast, lounge, and other services included that allow you to eat for free, even when on points. I did this in Korea two weeks ago and for a $175 hotel we had a massive buffet, filled up our bags with food for the day, and hit the lounge for dinner / booze. Restaurant quality meals for free (not exactly free, but you get what I mean!)
3. Figure out what is really important to you and be prepared to spend money on it. I'm frugal, but not cheap and many of the places I've been in the world I'll never be again. You can definitely go 'too cheap' when you're travelling and there are some expenses that are just worth it. I hired a car / driver in the Philippines for $50 / day and he drove us around for 12 hours each day showing us the sights, different parts of Manila, etc. The cost was reasonable and I saw more of the city and outlying areas than I ever could on my own. To me travel is a life-enhancing experience when done properly and I'm prepared to drop some money on it.
4. Use websites like flyertalk, rewardscanada.ca, to track deals as they always have substantial offers and the inside scoop on things. If you are hardcore like me consider downloading KVSflyer as it allows you to find the cheapest routes, fares, and ability to maximize upgrades or points. The full program is about $120 / year but I've saved at least $2K - $3k per year using it, and also gotten tickets worth quite literally hundreds of thousands of dollars more than I paid for them. Using this tool I've taken virtually every vacation flight in business class either through an upgrade from the cheapest economy fare or through creative use of my points. As an example I went Toronto - Tokyo - Manila and back for $950 round-trip and flew in business class both ways last year.
5. Do your homework. Many places outside of Western Europe and the US have exceptionally high quality hotels for exceptionally cheap (also possible in Western Europe, just takes more planning). In South East Asia, South America, and India you can stay in non-chain hotels for $10 - $40 / day that have nice interior, clean facilities, air conditioning and are safe. These are hotels, not hostels. If you do research in advance you can find these places and stay for very cheap at very nice places.
6. This is probably obvious, but use bloody public transport. I just came back from Korea, saw all of the major sights (my only major expense was $120 each for me and the gf to see the DMZ, which could have been $40 if we were able to secure seats from the USO). We used the subway every day regardless of how tired we were. Not only was it cheap ($12 each for four days) but it was exceptionally fast (3km cab ride took 20 mins, 3km subway ride took 5). GoogleMaps can give you directions using public transportation perfectly now and most systems in the world are incredibly tourist friendly.
7. Look for free attractions wherever you go. Most governments operate on a simple theory of tourism, which effectively goes something like this 'if we have cool shit, people will show up to our country to see it. We can then charge them shit tons of money in hotels, meals, transportation because they are dumb and don't consider these expenses when travelling. Therefore lets make the attractions cheap and suck the idiots in'. I saw multiple attractions in Korea (and everywhere else in the world that I've been) for what was effectively free to cheap (e.g., no more than $2-$3, and in most cases free). In many cities simply wandering around several of the local areas will give you a great flavour for the city and offers lots of interesting things to see. In others the national attractions are exceptionally cheap.
8. Travel in the off-season. I'm thinking about writing a book or blog called 'travel in the off-season'. I've been to Paris in the winter, Thailand in Monsoon season, Boston in the Winter etc. This isn't for everyone, but I've had fantastic deals with exceptional experiences by travelling in the off-season to almost everywhere I've gone. The pace is slower, the sights aren't as crowded, and the locals are friendlier in the off-season. These places tend to clear out in the off-season and we had a 5 star hotel in Thailand for under $90 / night and no one on the beach when we were there. The off-season comes with some potential weather difficulties, but they are minor compared to the savings (e.g., in Thailand it rained on average about one hour per day but we were able to take a break, have a snack and then head out again). If you go over Christmas, March Break, or other major world holidays to places you can always expect to pay a premium.
9. Stop packing so much shit. I always laugh at the airport when I see some poor family with 2 chubby kids, dressed in large hawaiin shirts and flip flops, mowing down on some unknown item from McDonalds, hauling 2 massive suit cases each out of the airport along with 2-3 sets of some form of sport equipment after returning from a one-week vacation. First, my question is always 'really, I'm supposed to believe that you are in any way athletic'? Second, how much shit do you need for a fucking week? It's fucking one week! I could get buy on a pair of pants, shorts, underwear and a t-shirt. WTF do you have in there, your entire home? Getting rid of the suit case lowers the cost of travel, makes it more fun because you aren't constantly thinking about hauling your shit around, and opens you up to a world of other things you can do. It also really eliminates the ability to buy anything while you travel which brings me to point #10.
10. Don't buy shit. Everyone has a tendency to say "I want to remember this trip with a souveneir". Guess what happens to that shit? It goes in your house somewhere and you eventually realize that you can't remember anything about it. Then you realize your house is full of useless shit that you can't rememer anything about. Then you think, maybe there's something wrong with me? Nothing wrong with you, just too much shit. Take memories, not things home. If you must buy something, wait until you're in an area where you can buy something local and bring it back that even if it is over priced is at least going to feed someones family. The purchase should be meaningful, not something you bought for $10 at a tourist trap.
11. Eat local, particularly in foreign countries. If you can't read the menu, that's the best place to eat. Avoid places with English waiters and translated menus, these are what we affectionately call 'tourist traps'. You can learn enough from a phrase book in 10 minutes to be able to say 'what is good here?' or 'I want beef', plus you have an adventure and the restaurants usually love it when you show up. They treat you like a king and you make some new friends. The locals always have cheap food, that is authentic and tastes fantastic. Don't worry about getting sick, just don't order anything raw (you can easily learn how to say cooked only) and don't drink the water (bring your own). I've done this in almost every country I've been too and paid 10% or less of the price in established places and had most of the best meals I've ever had there. Curry in Thailand for less than $1 including rice is a good example.
12. Potentially the most important one, but decide what travel is about for you. For many people travel has become, like many things associated with spending a lot of money to go some place and recreate the exact same environment that they have at home (e.g., a very high-end hotel where everyone speaks perfect English), along with gratuitous consumption (e.g., a cruise ship) or extreme luxury (e.g., an all inclusive resort). It has become synonymous with entitlement and the phrase I hear from most colleagues is 'I work so hard, I deserve a vacation I just want it to be totally easy and I'm prepared to pay for it. There is a lot wrong with this attitude, including the fact that if you wanted it to be just like being at home, why didn't you just take a week off and stay the fuck home? Anyway, that aside if you have a rough idea of what you want to get out of travel then it is easier to prioritize how you spend money. On a personal note, I really enjoy learning about the history of a country and eating / trying new foods. I spend most of my travel dollars doing things that are historically relevant and trying as many new foods as I can.
Anyway, some of these are practical and a few are philosophical. Apologies for the rant.