Travel Is Awesome!
Focus on the journey, not the destination. Joy is found not in finishing an activity but in doing it. ~Don Williams, Jr.
Far from being something to "skip over," wilderness travel is an interesting part of a story and forms a large part of many narratives, from Lord of the Rings to Star Trek.
From the 1e Wilderness Survival Guide to the more specialized 3e books like Stormwrack and Sandstorm, there is a lot of material to draw on in order to make wilderness travel more arduous and interesting.
For inspiration, I like reading historical travel narratives - ones that go through the jungles of Africa are especially juicy when it comes to ideas of how the landscape can terrorize the unwary traveler.
The rain falls upon the just/And also on the unjust fellas/But mostly it falls upon the just/Cause the unjust have the just's umbrellas ~Cormac McCarthy
It's simple, but get a random weather table and generate weather each day. (Obvious corollary - have seasons!) Climate has enough perils for most folks! In my current piracy-based Reavers on the Seas of Fate campaign, there's a lot of sea travel. Wind strength and direction can speed them on their way or stop them in their tracks; storms can provide vigorous skill challenges to a ship's crew! Getting wet, getting cold, getting overheated, getting fatigued all contribute to the wilderness travel feel, and give real bonuses and penalties the PCs can't ignore in combat. Have a combat in high wind or a rainstorm and apply the rules for it; it's quite a change of pace! And besides that, it is probably the single biggest addition to the sense of realism, to have variation going on independent of the PCs' actions and desires. Makes the world seem bigger than you are.
My time in the Boy Scouts taught me that Nature has but one goal - to kill you. ~Me
To get along in the wilderness, you need food, water, and gear. If you're not familiar with the land, you will end up having to backtrack around (or walk into if you're really dense) rivers, ravines, animal/monster lairs... More esoteric threats like quicksand also dot the landscape. Disease is always a threat as well. Insects plague people (and bring more disease) in many different terrains and seasons.
This is a great opportunity for those Survival and relevant skills to come into use. I prepare lists of "random encounters" that are more mundane than monster stuff and make them (and monster encounters) dependent on Survival checks. Skilled woodsmen don't walk into an owlbear's territory or drink too much from water in a cave.
Not all those who wander are lost. ~J.R.R. Tolkien
You also need maps or guides - besides avoiding trouble spots, it's really quite difficult to find your way across trackless wilderness. Plenty of people get lost on reasonably well blazed hiking trails in the modern day, and having a map (and a compass, and other stuff) in no way guarantees you can't get lost. Time for Survival again!
In my pirate campaign, I require a whole lot of navigation rolls to find things, even when on a chart. It's very not simple. And when you get lost, you run into other stuff, you take more time to get there, you get more wear and tear...
Travel is glamorous only in retrospect. ~Paul Theroux
Wilderness travel is tiring and wearing, and not just to the people, but to gear as well. If they spend a lot of time out in the elements (and especially if they ignore rain, bogs, etc.) then their gear will degrade.
But mainly people get tired. Some of it is from the elements and disease, above (note that in 3e, a lot of the heat and cold stuff ends up imposing the fatigued condition). I'd consider giving nonlethal damage or even ability score damage from some of the natural threats from the "Survival" section above. "Stinging gnats - Survival DC 15 or 1 point of CHA damage."
Then, finding safe places to hole up and rest can provide mini-adventures of their own.
Travelers never think that they are the foreigners. ~Mason Cooley
Depending on the region, someone or something lives there. If it's free of people, it's probably large herds of animals of various sorts that definitely provide obstacles and threats. But usually it's people. Many of these people don't like visitors and may attack, or demand tribute to pass. Or they do like them, and insist they come, eat, interact, get hit up for various stuff (and if rejected, get hostile). And you're a lot more likely to come across inhabitants than just as "wandering monsters" - the more-hospitable points of the terrain you'll want to travel through, camp in, get fresh water from, etc. will be hot spots for the locals too. And word spreads; if you slaughter/give syphilis to/give loads of money to any given village, the ones nearby will find out quick. Local culture is as much part of the landscape of a trip as the real terrain features, and should be memorable.
I fondly remember the Night Below game I ran where the PCs stayed the night with some friendly gnomes in their burrow. Their elder told them a chilling story about the legendary dark elves, and mentioned that their caverns once extended to below this very burrow... When a dark form broke through the dirt wall of their room that night, the wizard freaked out and Color Sprayed the party fighter into a coma. Of course it was just a puppet on the end of a broomstick being pushed through by giggling gnomes in the next room. I'm pretty sure that the players as well as the characters still have the emotional scars from that session.
I have found out that there ain't no surer way to find out whether you like people or hate them than to travel with them. ~Mark Twain
I still remember the 2e game where the PCs holed up in a rural inn for two days waiting for a big rainstorm to let up; as the stir craziness set in they got up to shenanigans more interesting and memorable than the adventure at hand. Not quite the Donner Party, but getting there.
Travel is often an opportunity to slow the pace and have PCs interact with each other (assuming you're one of those weirdos that does such things instead of just slaying monsters). Once you hit cities it's intrigue central; once you hit the dungeon it's hardcore killing action. It's during the journey that you can get PCs to take the time to develop themselves by talking with others.
And it's just gold if there are regular NPCs with the party - this is the time for their personalities to develop, for drama and seduction and all that Real World/Survivor/Insert Your Favorite Reality Show Here kind of stuff.
Unless you know the mountains and forests, the defiles and impasses, and the lay of the marshes and swamps, you cannot maneuver with an armed force. unless you use local guides, you cannot get the advantage of the land. ~Sun Tzu
If a fight happens, don't let them forget where they are. In the wilderness, nice level stable footing is the exception not the rule. Maybe it's raining, maybe they're on a riverbank, maybe it's 8 PM and it's twilight, maybe they're in a marsh, maybe there's hanging vines everywhere. Once it goes all combat encounter, you should under no circumstances have everything morph into a featureless battlemat. If you do not weave the description of the surroundings into your GM descriptions at least once per round, you're not doing it right.
And keep in mind the locals know the terrain and will use it to their advantage whenever possible when engaging the PCs!