I ran a 4th-Ed game for a couple of years. What follows will be informed from my experience running that campaign. My campaign was made a mix between the real world and the base 4th-ed "canon", so my examples will reflect that.
First off, while a map is not necessary, I think you should sit down and get a rough idea of the world/continent/area that the game will involve. Given that a picture is a thousand words, a rough map helps in the same regard. Less detail far away, and more detail (but still rough) in close. All I knew about the America of my campaign was that the indians were shifters, and the Aztecs were dragonborn. For Europe I knew the shape of the continent, the mountain chains, and the major cities. And then for the area of Germany where the campaign started I knew the major towns (on that scale), and the major geographical area of interest (The fey-ridden Swartzwald, the snow-capped Alps, the Hûrghills).
The exploration itself was generally goal-driven. The group need to kill a monster, to get information, to secure an artifact, and the goal happened to be in a location with no teleportation circle. This happened often, given that I had only put teleportation circles in the capitals of Europe. Everything outside of that needed travel, either by trudging along roads (which we generally quickly skipped past), through wilderness (interesting through encounters with locals or wildlife, or through spot-light features) or through neighbour planes like the fey-wild (with weird terrain to add to the standard features). Through the goal I generally had a rough idea of what they were going to do, and could plan the travelogue appropriately (though if you are going free-form it is important to have that rough idea of neighbouring areas, so you have something to improvise over if they wander out of the planned area or path).
Now, I'm not sure that I've got down the art of the travelogue. Sometimes the player's just wanted the journey over with, and to get to the actual accomplishment of the goal. However, the way I did it, there generally were two levels. One is the actual travel. I'd give the player's a quick description of the landscape they were traveling through (including whether where appropriate) and then fast-forward to the next encounter or spot-light feature ("You travel through this miserable landscape for three days until). The fast-forward could be weeks or could be hours, depending on the scope of the scope of the journey.
Then they run into an encounter with locals, wildlife or a spot-light feature. In Siberia they might run into Kossack Orcs. In Arabia they might run into a battle between to feuding Bedouin tribes. The important thing is that this is not just a filler encounter. It means something. They get to know what tribes are in the area, and interact with them either peacefully or not. They learn that the wolves in this area will attack an armed convoy, and this will color the following journey, especially if you mention how they get attacked several more times in the following fast-forward.
The spot-light feature in the same way is something that worth noting, big or small. They might set camp by some warm springs (which would be a very short spot-light). They might reach the Great Wall, and have to figure a way past it. Or they might encounter a ruin from which strange lights emanate, and decide whether to investigate or go past. The feature should either provide color to the geography of the world (warm springs), the lore of the world (the ruin left behind by the ancients) or both (the Great Wall stretching from the Himalayas to the ocean, crafted by the dwarves under the servitude of the ancients).
Once the group has dealt with an encounter or a spot-light feature, you fast-forward again to the next encounter, or finally to the goal. If the group crosses into new terrain, you comment on that. Sometimes during the fast-forward, the group might also encounter other people or animals without you having to make an encounter out of it: "As you get closer to the mountains, you see more and more dwellings, and start to meet other travelers on the road.", "As you continue your journey you continue to be hounded by wolves, though you never experience an attack as large as the first."
Now, all this actually covers travel from one location to another. If you want more traditional dnd wilderness exploration, you will either need a map, or you will need to pretend that the exploration is freeform.
If you are just pretending, you can more or less follow the above structure. You have some spotlight encounters and features that you want to display, and you do so as they trudge around aimlessly trying to find the goal. Once you've displayed your stuff, you then let them find the goal.
With a map, you can have more of a mix. You can decide that "this feature is in this area" and "and that feature is around here", and then track the party around. But given that formula, there is no guarantee that they won't just miss all the stuff, unless you supplement the stuff with at least as many clues (they'll be ambushed by lizardmen anywhere in the swamp, and the lizardmen's tracks will lead back to the pyramid).