Get a hex-based map. Record it in miles. Give the PCs a hex-based map. As they move, you tell them what they see (if there are three hexes of plains to their right before a forest, tell them that - odds are they can see for a while, especially if they're on a hill).
Make up a random encounter table for the terrain types. Only make 25% of the entries combat encounters, and make some combat encounters BIG and some super small ("Oh, geez. One zombie? Do we even need to roll initiative?"). Other encounters should be role-playing (A merchant passing through), flavour with no game effect (describe a herd of buffalo passing by), interaction (a ruin, a puzzle, or some other knick knack that PCs can explore, or pass on by), challenge (a chasm that needs rope to cross, a sinkhole, quicksand, or whatever), and weather/terrain effect (a sandstorm in your desert, or a small earthquake, or a volcano).
A note about combat encounters - it's better to make encounter checks a few times per day. This will mean you can expect MAYBE one combat encounter a day. Your Players will quickly learn this, and will blow their dailies during it. This is fine, and actually makes the fight fun. When prepping encounters, though, realize that your "average" wilderness encounter should be considerably tougher than your "Average" dungeon encounter. This, by the way, is keeping true to earlier editions of D&D.
However... DON'T go crazy with combat encounters - 4e is grindy enough!
Next, make yourself a deck of cards. On each card, write down something like "hole in boot", "Bad water" or "Blood poisoning" - bad things that can happen to a character if they're not careful in a survival situation. Every day the PCs are in the wilderness, draw a card and note the result. If a PC finds himself in a situation where that specific event could happen (i.e., they refill their waterskins without mentioning preparing the water, and you drew the "bad water" card), the event happens. It can either make PCs paranoid in their explorations (in which case you should relax things a bit, or accept a "standard operating procedure" list from PCs), or bring wilderness exploration to life.
Have certain events require PCs to carry certain gear - if they don't have that gear, make an endurance check... failure means you lose healing surges for the next day. If you sleep in the rain, you'll be sick the next morning. If you don't bring real food and rely on trail rations, you'll get sick. Proper food is important, and trail rations are far from "proper"
(Side story. A few camping trips ago, we ate nothing but hot dogs, chili, tea, and potato chips. For three days. WHen I got home, it was like I had dysentery. True story!)
Okay. So PCs are moving along this hex-based map, and have to keep track of a few things. Here's where it gets interesting. Put in choices as they move. Do they stop in this cave earlier in the day than they like, or do they keep moving on despite those storm clouds, risking getting caught in the open if they can't find suitable shelter? Do they explore that ruined tower? Do they follow the trail to the dungeon, or do they take a "shortcut" through uncharted forest and save a few days' of travel?
Another fun trick, though it takes some time setting up, is to roll DCs for terrain against a flat passive nature check (sort of like how you roll stealth checks against a flat perception check for monsters). Write these on every hex - whenever the PCs enter a hex with a higher "check result" than the highest passive nature in the party, they get slightly lost, and you feed them false information for mapping purposes. That's a fun one.
A good trick is, whenever you get spare time, make mini-adventures on your computer - as in, two or three encounters. Set them up so they can occur in a variety of situations, and then print them with a listed level (one a few levels higher than your party's current level, for maximum useability). the trick here is, you drop a hook for the PCs, and if they take it, the adventure happens, and if not, they go about their business. If you set each adventure up with varying hooks, you can re-use these mini-adventures until the PCs finally engage in one (without ever knowing it was the same adventure!). If the PCs are below level when they bite the hook, adjust the monster on the fly (it's easy), and if they're higher level, do the same.
These are just a few ways you can make exploration more fun for your group.
