The handwave and a quick flavorful paragraph that encapsulates what the journey is like works like a charm. However, if you want something more epic, I suggest:
- Use random encounters, but improve your random encounter tables. Make them not just hack and slash. Customize them to your campaign's mega-plot. Write out a mini-adventure for each random encounter. Include recurring faces/themes.
- Use a "montage" approach. Give the PCs some goals to accomplish during their travel, and some options to choose during their travel, then run mini-scenes showing the PCs engaged in some action related to their travel. Some examples:
* The rogue PC goes through a foreign city talking to contacts to track down the fastest ship and determine which ship their quarry left on
* Learning how to man a ship and becoming friends with the crew and captain, only to learn they're wicked pirates who have several people kidnapped below deck
* Dealing with savvy desert merchants, selling their horses for camels
* Do we go over the hazardous mountain path and brave the storm giants or do we sneak through enemy territory in disguise risking capture and execution?
* Sneaking past a guard station where a toll for using the road is collected
* Navigating a hazardous section of river
* Bartering with a ferryman while pursuers are hot on the PCs' trail
* Two of their griffons get into a fight while they set up camp and are injured so that they can't travel unless healed, and the two griffons need to be kept apart
- If the PCs will be traveling through territories native to their PCs, you might let them come up with some ideas. What is their homeland like? What is the mood there? What kinds of problems would travelers have to deal with? Who does your PC know there? Maybe even allow your players a 30 minute spotlight at DMing when the group arrives in their PC's hometown...if it suits your group's play style that is.
- Make good use of the overland travel rules in the SRD. But rarely make it simple. Require the PCs to travel by side roads, foraging for food, while evading a group of pursuers. Make them contend with the elements: Do we dock at the pirate town or risk our lives in the monsoon? This allows the ranger to shine, especially the variant rangers out there.
- If the PCs show interest in the various settings of the world and enjoy shopping, the bazaar is always a great way to showcase local flavor. It's not just a many-pocketed silk vest...it's a wizard's vest of the Artua Academy emblazoned with sigils of that noble house. Or the holy water from the Green Lady's Font also has the power to act as a bless growth spell if poured on a field. Appealing to a player's pocketbook/power gamer is always a sure way to introduce flavor. And merchants themselve very widely too.
- Allow those PCs who know obscure languages to put them to use, perhaps even acting as translator for the rest of the group. Perhaps include one or two samples, if not of the foreign langauge itself, just some simple words (e.g. ghazwa refers to "raid", but has only positive connotations) or popular sayings (e.g. Westing means dying).
- One of my favorite things back when I played Al-Qadim was to unfurl a beautiful 4, 6, or 8 panel map for the PCs. I taped the map to piece of corkboard. Each player was given a different colored thumbtack to which they attached a piece of paper with their PC's name. Usually the group was together, but at one point it was very split up. Allowing the players to move their thumbtacks when they traveled really added that epic feel to the game.
