Maps are the most common way to guide players around games. Other methods include beacons, landmarks, a compass, trails, and many other things.
Another option I rarely see is what I'll call gradual indicators. By that I mean, a visual feature becomes stronger/weaker or more/less common as the player nears certain places or objects of importance. These gradual indicators can lessen or even negate the need for UI methods which distract from the gameworld.
For example, elevation can be used in this way. In Rise of the Argonauts, the player knows whether he is running towards the palace or the docks of Mycenae by whether the path is sloping upward or downward. The same method can be used in any number of settings, including dungeons and roads. The degree of a slope can be telling, too. If two paths both lead up a mountain, one can be recognizable from the other if it is significantly steeper.
Vegetation can be a gradual indicator. Grass and shrubs might grow tall in one area and shrink or die out toward another. Oaks might dominate one area while mesquite trees dominate another. Both trees might habit an area, but the ratio between them could indicate to the player in which direction he is headed.
Architecture and objects can be used in the same way. The facades of buildings and their relationships to each other (such as how far apart they are) can indicate if the area the player is proceeding toward is wealthy or poor, old or new, damaged or undamaged (by war, weather, or graffiti), and so on. Statues and decorations can change in frequency or in subject through an environment. The type of shops or their names can change in style and tone.
Even audio can lead players. The roar of a waterfall or pounding of waves can gradually rise in volume as the player nears them. Likewise, the sounds of animals, the firing of weapons, the chatter and laughter or shouts of NPCs, or a thousand other things.
Animations and even environmental A.I. can guide players. As a player nears a battlefield, he might increasing notice NPCs crouched over and weeping. Or NPCs might be increasingly erratic and skittish... increasingly distressed as the player nears the source of that distress. The NPCs might pace, look around fearfully, or chatter to themselves. Think of the A.I. in Batman: Arkham Asylum and how the Joker's men act differently as they become more aware of Batman's presence and are afraid.
There are countless forms gradual indicators can take. The goal is to help players navigate environments without having to take their eyes off the gameworld or see anything that takes their attention off the story they're experiencing.