Use a dungeon with an interesting map
If the map has several levels, hidden entrances, ways to see into other rooms without easy access, stairways, or simply loops, players can use their map (that they draw or you provide) to deduce where corridors and doors might lead to.
If the dungeon is visited several times, then the navigational choices are no longer arbitrary - the players know roughly what they will find and where.
In order for this to be meaningful, the dungeons has to be large or it has to change, perhaps due to being re-settled, or the context around it has to change. Maybe the players slaughter an orc settlement but fail to find the secret door to their temple and the older complex underneath, only later finding hints about the missed parts. But by then something else has settled in, or some tunnels have been lost due to lack of maintenance, etc.
Scouting, prisoners and interrogation
Scouting and acquiring information is often possible: listen at doors, use magic and talk to the vermin, listen rumours about the place, have someone sneak in before the others and come back when they know what there is to find.
If the players kill everything they meet, they are going in blind. Take prisoners, talk to them, have them show the way.
A logical dungeon
If the dungeon has living and active creatures, they make noise, leave tracks, produce waste, and shape their living environment to fit them. They will also create some sort of ecology, or lack of it, around themselves - vermin, prey and predators. Remember this when describing the locations, and players will naturally be able to deduce things about the dungeon.
If the dungeon was constructed by intelligent, even if bizarre or insane, minds, then it has some kind of basic internal logic. Do not hide this logic actively. If the players figure it out, they can make predictions based on it. This can range from the obvious (frequently travelled routes do not usually have active traps) to the obscure (the cult that built the place had three as their holy number and two as the unlucky one, which is reflected in the placement of trapped doors and treasure chambers).
If the dungeon has a history, then that, too, will be visible there, and players can, with luck and cleverness, figure out and use some of it to navigate.
Most important: Make it matter and tell them it does
Does the game offer strategic depth? If the dungeons are essentially linear, with maybe a few side branches, there no navigational decisions to make in the first place.
The dungeon should also have things they want to find (treasure, other objectives) and things they want to avoid (dangerous monsters, heavily trapped areas). If everything is balanced, then it does not matter where one goes.
If the dungeon is too small, there is little opportunity for navigation.
Related to the last point, if they are going to visit the entire complex anyway, navigation is typicallly not so important. (It can be, if a particular holy sword makes killing a particular vampire a lot easier, or an area is much nicer if approached from a specific direction, and in other specific situations.) There should be places the players will not have time or resources to explore. This can be due to time pressure, several possible smaller dungeons, or a large megadungeon.
After this, you should inform the players of the reasons you have implemented to make navigation meaningful. Maybe they are used to it not mattering and simply have not considered the possibility.