Some of the below my delve more into house rules, but nonetheless...
RJ's Top Ten Tips for Interesting Overland Journeys
1) I let the group's ranger make a Wilderness Lore check to determine how good of a campsite is located prior to darkness setting in. I've contemplated doing this roll myself, but I figure the ranger would know if she's found a nice spot or not. Things such as the presence of fresh water, escape routes, good look-out points or climbable tree, defensible position, etc. - all of these characteristics should be factored into the roll. Then I use the resolved site to help determine the chance the party will be interrupted during rest by a wandering encounter.
2) Weather. Never underestimate how successful minor details can be; they add the proverbial spice to your campaign world. Every day isn't sunny and clear. Reflect the climate and the geographical position of your party. You can randomly roll weather or arbitrarily decide it on your own (either method should be transparent to the PC's). "A light, cold drizzle" that forces the party to endure a cheerless and fire-less lunch can make the day memorable, especially when the group is trekking for many days at a time. Such little things are great for creating a mood.
3) Random encounters are not always bad. Add flavor to your world. The PC's aren't the only ones traveling. There's more in the countryside than bandits and orcs. Merchants, patrols, other wanderers, etc. likewise use common routes. Perhaps a peasant with a cart of apples sells some to the PC's and invites them to stay at his farm up the road? Sometimes the best roleplaying encounters are those unplanned. The party can trade information with groups who may be heading the opposite direction.
4) Accentuate skills that are less used than others. A log across a stream begs for a Balance check and perhaps some humorous results if the wizard falls into the icy stream. (What happens to the ink in a drenched spellbook?) Not every failure has to result in hit point damage. Perhaps someone with Knowledge (Nature) notes the terrain is perfect for some rare herb, and someone with Knowledge (Herbalism) knows exactly what the flower looks like. The herbs need not be magical - and probably shouldn't be - but it doesn't mean they aren't somewhat valuable; perhaps the PC's can spend a few hours gathering the rare roots to sell in the next town. Fighting on horseback can be hell for those who haven't spent the requisite skill points; make untrained characters feel the pain while rewarding those who did spend hard-earned skill ranks into Ride. Mileage varies, of course, with how gold-piece poor or how into roleplaying your party may be.
5) Accentuate feats and racial abilities. Your gnome can talk to burrowing animals once per day. Has he ever used that skill? Maybe a mole warns him of danger ahead. Your ranger can collect food for the party if given enough time. Players who select Druid or Ranger as a class should be allowed to shine in overland journeys.
6) Charge 'em gold. You want to travel the Kingsroad? Fine, but you better have a couple gold pieces set aside for the King's patrols. In exchange for the money, the party may get writs allowing them passage on the roads for a certain amount of time.
7) Make your world's landscape an NPC. Most campaign worlds are old and should have a history much like any NPC the party may meet; the roads and wilderness trails have been traversed by hundreds of creatures prior to the PC's making the journey. An old wooden holy symbol affixed in the soft ground that marks the grave of a peasant's child can add poignancy to a dreary wood without requiring combat or melodramatic descriptions. Perhaps the party stumbles across an ancient stone monument, half-buried in the sod and leaning forlornly to one side. Here's a chance to use Decipher Script to see what the runes say. And maybe the road parallels a forgotten highway from some lost Empire - the PC's can still see random cobblestones hidden amongst the thorny weeds, and white marble mileage markers to the side of the road. Where does it lead, and why was it built?
8) Maintain consistency. If the party was ambushed by orcs in a wooded glen and defeated them a tenday ago, have there be spent arrows and perhaps a few stains of blooshed on certain rocks when the party crosses the same spot on a return trip.
9) Make the wilderness a monster. There was a reason many medieval battles were fought at fords in waterways, passes in the mountains, or chokepoints in swamps and forests. Crossing a flooded plain or river rapids should be difficult and dangerous. PC's that spend too much time in fens or swamps may very well attract diseases. Obviously, again, you'd tailor this to your campaign - just how realistic are you? Do all your PC's have nice white teeth and never get sick? Or could players without appropriate gear catch a cold that could spiral into pneumonia?
10) Keep track of food. This is true for players and their mounts. Make the ranger use his skills to feed the party, and make the group suffer if they're ill-prepared to handle the travails of a long overland hike.
Cheers,
RJ