A point of note: the danger of maps that are fully uncovered is that the player might not know where he's been already. In such cases it's often useful to show the entire map but display unvisited areas differently to give hints as to which places to check out if the player is stuck. Ultima Underworld: The Stygian Abyss provided the players with the ability to add comments to the map. This could often be used to mark areas that were already investigated and explored.
In games where discovery is important, uncovering areas of the map can be fulfilling. The player first has to find out about the environment, and sometimes finding pieces of the map can even be a reward in itself.
For example, in Metroid Prime 3: Corruption, the levels are peppered with secret rooms. In this game the player can unlock all the rooms of the current level on his map which makes it a lot easier to find these rooms. Here the map becomes part of the reward system.
A negative point of note about this map, though, is that it is in 3D, which makes it a bit hard to use. It's still quite good compared to other attempts at 3D mapping though. For example, the map in Splinter Cell: Chaos Theory is in 3D, and it's anything but easy to use. Using 3D makes it much harder to quickly understand the complex space -- which partially defeats the purpose of the thing in the first place.
Of course, video games can also create impossible spaces that are very difficult to map in a way that is easily understood: Corridors that return the player to the starting position, even though they are a straight line, or doors that lead the player to different places each time they're opened. In these cases, a map is usually not much of a help, especially as these designs are often meant to intentionally confuse the player.
The next type of tool is what I've dubbed "markers". A marker highlights a certain position or area in the world through a discrete interface element. Kind of like "augmented reality".
Note that this element can be a 2D graphic or 3D model. Also some markers are also only visible when the associated object or place is visible, while others can be seen even through walls and other obstacles.
Markers are very useful to lead the player to a certain position in the world -- even if it is in motion. Because of they are often used to identify important areas of interest, like the positions of teammates or enemies to make it easy to reinforce, engage or evade. Or they draw attention to objectives or other places of potential interaction.
For example, the exclamation mark icons over the quest givers in World of Warcraft are what I would call a marker. They make it easy for the player to navigate to important places where he can interact with the game.
Another example of Markers would be Left 4 Dead, where icons are used to highlight critical resources (ammo, weapons or "peels") and places of interaction (crescendo moment triggers).
L4D also highlights the locations of your fellow teammates with a halo around their forms, with the color displaying their current state. And last but not least, when a teammate can be brought back into action, a silhouette shows where the team has to go to free him or her.
Another well done use of this can be found in Unreal Tournament 3. Here, players new to a team-based multiplayer map can activate animated help arrows which show the way to the enemy flag. This is a good way to quickly teach new players the maps. This idea of marking the path rather than the target is also used in the help system of other games such as Army of Two and Dead Space.
An unconventional example for a marker are the red objects in Mirror's Edge. These change color to highlight the obstacles the player can interact with. This is straddling the line between immersed and discrete tools, since we're talking about objects that are a part of the world. However since these change color as the player approaches, they are definitely interface and not a part of the world itself.
Apart from those examples I also want to highlight -- pun not intended -- another game's use of Markers: Anno: Create a New World for Wii. In Anno, the game sometimes places position and/or area markers to point to certain positions. This is used to show the player where to build his first house or where to steer his ship in order to advance the story.
However, the top-down view in Anno can only display markers when they're on the screen. If you don't look at the destination you have to steer your ship to, then you won't see the marker, which doesn't help much if the player has to find the spot in the first place. And that's where the next discrete tool comes in.