Physical fitness takes time to build up and maintain, but makes travel easier. Running through an airport with a suitcase would be much easier for a traveller with good muscles and cardiac strength.
Make sure you have shoes your feet are used to. Travelling often involves much more walking than at home, and getting blisters or aching ankles can hinder you from enjoying the destination in full. This is especially important with hiking boots and if you intend to hike.
While the social stigma of obesity is mostly restricted to modern times in the Western world, and weight alone tells little about a person's health, achieving or maintaining a healthy weight might make travelling easier. If you are overweight, then getting an inch or two off your waistline can produce noticeable improvements in your energy level and physical comfort while travelling, even if you think you need to lose much more.
This article will avoid attempts to crown the best form of exercise, except concluding that any exercise is better than none at all.
On the roadEdit
Sitting for hours in a car or bus, or on a train or plane strains both body and mind. You should get out of the seat at least every two hours, ideally more often.