Flights
I am an early bird for buying tickets. I always get cheap prices with low-cost airlines. I also have a good credit card (reward program) with that airline, basically 3-4 flights in a year are free for me.
Hotels
I am in the tourism industry, working intensively with other B2B hotel providers. That gives an extra to get cheap deals or compensational stays.
Time
I don't have huge vacations. I use my day-offs on Fridays or Mondays which gives me 3 days of travel time. Generally moving around Europe, so flight times allow me to do that.
If the flight time bigger than ~4 hours, then I will stay in that country longer. Spending a huge portion of my yearly vacation is not sustainable so that's one or two in a year. Lately, I have been in Thailand and it was 9 days.
Other expenses
I don't eat at luxury restaurants. (Exceptions: cheap countries like Ukraine, Hungary etc.) Even I buy sandwiches from supermarkets on lunch.
I don't pay anything to museums. Not really a cultural guy, therefore, I don't spend any time or money on museums.
I walk! I never use taxis. (If it's not a business trip and can't expense it.) If I can't go where I headed on foot, I prefer subways, buses. Also, in some countries (Netherlands for example) I rent bicycles to move around.
Everyone can do these things actually. You just need to follow promotions and give up luxury. :)