In my 4E games, exploration is just a natural result of me not giving the players enough clues to decide on a "correct" path, but giving them lots of landmarks to seek out, all with their own unique challenges.
A simple example:
"To the South, there is the twisted jungle you just left. To the North, there is a sheer cliff, sixty feet high, and beyond the cliff there is the crater you seek. On the West side of the cliff, the jungle behind you spills over the side, creating a waterfall-like cascade of vines and roots. To the East the sheer cliff is partly shattered, providing a perilous but perhaps passable path, if you can keep your balance."
Both the West and East path feature climbing challenges, but West path provides a challenge especially suited for druids, shamans, and anyone creative enough to try something with the roots and vines or even the trees themselves. The East path provides more opportunities for a Dungeoneer, but also provides some options for the more destructive sorts. A creative enough player could even take roots and vines from the forest and try something clever with those. A less subtle player could have just ignored both West and East options and just found a way to blast the cliff face directly and turn the cliff into a rocky hill. A more curious player could have just kept on circling to try and find another way down further to the West or East.
Moreover, these challenges are all slightly different on the way back, since they'll have access to different resources at the bottom, may have damaged the climbing options on the way down, and may be weighed down with equipment or creatures - or riding them.
