Gehennom contains a large number of maze levels. Maze levels always fill the map, unlike dungeon levels, and you can only map a few squares per turn by wandering around. Digging is slow, because wands or spells of digging can only dig 1 square per-shot on a maze level.
This has given Gehennom a reputation as a slow and boring phase of the game. But the amount of work involved can be greatly reduced by good strategy.
Depending on your role and equipment, mapping can be made a lot faster, but writing and using a lot of magic-mapping scrolls uses up marker charges, which is a luxury which can't always be afforded. Since fast mapping of Gehennom is a luxury, most players will want to expend minimal resources on it—wishing up a spellbook of magic mapping is not cost-effective unless you really have wishes to burn.
Alternate level method[]
This is a way of simply halving the effort required to map Gehennom.
Observation: If you map a level, either by magic mapping, or manual exhaustive search, you find both the upstair and the downstair.
Observation: going down the downstair on level N puts you on the upstair of level N+1; going up the upstair on level N puts you on the downstair of level N-1.
So, if you map level N-1 and level N+1, you can find the stairs on level N without mapping it - go down the downstair from N-1 and you find its upstair, and going up the upstair from level N+1 gives you its downstair.
Conclusion - if you can map level N, N+2, N+4, ... through Gehennom, you get all the others for free.
Typical application of the alternate level method is: you arrive on level N+1 by the stairs, so you know where the upstair is. Step aside & dig down, falling through to level N+2. Map N+2; go to the upstair, go up, and you now know the downstair for level N+1. Go back down, go to the downstair for level N+2; go down to N+3. Rinse and repeat.
A source of digging is therefore required. I normally carry a pick-axe, so I don't kick myself later on for using up all the wands of digging. Note in particular that, because you don't fully map level N+1, you don't know the most efficient way between the stairs, so you usually need to dig a path between them; this can get expensive on digging, so a pick-axe is recommended.
One caveat with this strategy of mapping only alternate levels is that later on, when you are dragged down by the mysterious force, you may land in an unmapped area of the level. Therefore, it is a good idea to have teleport control so that you can teleport directly to the upstairs when this happens.
Finding Vlad's Tower[]
If the castle is at level C, you may need to map all of C+9 to C+13 in order to find the upstair leading to Vlad's (which can't be found via the alternate level method). If you aren't short of mapping, do them all as you encounter them; if you are tight for resources, do C+9, C+11, C+13 as per the method, and only go back and do the others if you haven't found the stairs for Vlad's yet.
Known levels[]
If you are happy to be spoiled by reading the Gazetteer, or have played through Gehennom before, you'll know the layout of the major demon lairs (listed on Special level). So you know where the downstairs are on those 4 levels, and know roughly where the upstairs are. So you can treat those levels as already-mapped; if you find a demon lair on level N, you can restart the alt level method from there, mapping N+2, N+4 etc.
If you get lucky, you find demon lairs on alternate levels, and don't have to do any mapping at all.
The vibrating square level[]
Most players will want to avoid mapping the level with the vibrating square. So once you are below the fake wizard's towers, switch to just digging down until you hit rock bottom. Hopefully that's in just 1 or 2 levels, otherwise you have a trickier job heading up mapping to find the upstairs (you could level teleport back above after finding the VS and go back to applying the alternate level method, once you know which level the VS is on).
Mapping equipment[]
Depends on the equipment you have.
Spell of magic mapping[]
If you have plenty of magic power, no need to be clever, map every level.
But most non-wizards don't regenerate magic power very fast, so have to be more economical. Use the alternate level method - it greatly reduces the number of levels you actually need to cast mapping on.
Wishing up a spellbook of magic mapping simply isn't worth it - wish for a magic marker and write Scroll of magic mapping as you need them - cheap to write.
If playing a wizard, while you can write a spellbook of magic mapping, this is normally not cost-effective; for the ~36 marker charges it uses on average, you can instead get 6 mapping scrolls, so assuming you have around two mapping scrolls already in stock (you'll usually have found a few during the game so far), you get maybe 8 mapping scrolls total which is enough for Gehennom using the alternate level method. And the cost is on-demand instead of up-front, so if you suddenly desperately need something else instead, you haven't used up the option; and mapping scrolls can be squeezed out of almost-exhausted markers, whereas magic mapping spellbook needs a marker with 50 charges in to be safe.
Scrolls of magic mapping[]
This is the main strategy. Most players will have got a magic marker, by finding or wishing; and most will have found 2–3 mapping scrolls by chance earlier in the game.
Use the alternate level method; to map, use any scrolls of mapping you have first, then write more if you have charges to spare and some blank scrolls. Usually by this late in the game you have already done any armor/weapon enchanting, got all the stuff you need, so you don't typically have anything to save marker charges for (except perhaps for portal detection - don't forget).
Clairvoyance spell[]
If you can't afford enough mapping scrolls, next best is clairvoyance. The spell requires only basic skill in divination to cast well. In your mind divide the level up into roughly 8x2 chunks, aim to get to the middle of each chunk and cast the spell to minimize overlap in the 10x10 area revealed. It reveals the layout of the maze and reveals any stairs in range.
Clairvoyance extrinsic/intrinsic[]
You can also get clairvoyance as an extrinsic or temporary intrinsic. This causes the same effect as the clairvoyance spell, but it occurs at random intervals instead of under the player's control. This doesn't cost any magic power or require any magic skill. The best way to use this seems to be to wander around like you are manually mapping, but don't worry about exploring every corner and instead try to push into new areas so you get more mapped by each random clairvoyance.
To get temporary clairvoyance, donate 200*XL to the priest of Moloch in the Valley and get clairvoyance for 500-999 turns per donation. Two or three donations can give you enough time to map out a significant portion of Gehennom, especially if you go relatively quickly to minimize the amount of overlap of each automatic "firing" of the clairvoyance.
Wizards can get extrinsic clairvoyance by wearing a cornuthaum. This certainly isn't worth a wish, though, since you can wish for a marker and write magic mapping instead.
Note that the Amulet of Yendor also gives extrinsic clairvoyance when carried. But once you have the amulet, you can't do the alternate level method, and you are being harassed by the Wizard, so most players will prefer to have mapped out Gehennom before that.
Manual search[]
Exhaustive manual exploration. Tedious, but if you don't have the marker charges to spare, this is your fallback.
Note that you are still better off using the alternate level method - much better off, if you value your time. You're only having to manually explore half of the levels; equivalently, it is a better use of time to search a whole level looking for 2 (or 3) stairs than to be looking for only 1.
Manual exploration time is reduced maybe 25% if you have a lamp, because you can see that bit further and don't need to walk down to the end of every little side passage. A magic lamp is ideal, since you can just leave it on; an oil lamp is okay, but you want a lamp for the ascension run, so be careful not to use up your last lamp. But if you have a lamp or potion of oil to spare, just keep your lamp on (except when retracing steps).
The Eyes of the Overworld are better than a lamp, but certainly not worth wishing for just to help mapping—a magic marker to write mapping scrolls is a better wish.
Manual search does have advantages. Firstly, Gehennom has a fair amount of equipment lying around - and if you are short on mapping scrolls and marker charges, perhaps you are short of kit generally. Blessed potions of object detection can be used to detect items around the level & reveals the type of some items; as you are wandering around the level, and the stairs are just as likely to be in one place as another, you might as well start by heading towards any interesting items.
Watch out for fire traps - if you don't have intrinsic searching, you are likely to get burned a few times. If you have high luck and bless your cloth/leather armor items, they are unlikely to get burnt.
Demon mapping[]
If you have cold resistance, telepathy, teleport control and enough sources of teleports (ideally the teleportitis intrinsic) then you can let Asmodeus find all the upstairs and downstairs in Gehennom for you once you have found his lair. The cold resistance is needed so that Asmodeus can't hurt you as you chase him up through Gehennom.
With Asmodeus next to you, level teleport to the vibrating square level (specifying level 70 should work). Hit him until he teleports away to the upstairs, and use telepathy to see where he is. Teleport next to him and hit him until he runs upstairs. Follow him and repeat this procedure until the stairs on every level are located. It is a good idea to use a stethoscope to make sure you don't accidentally kill him.