To get the Amulet of Yendor, you need four things: 7 candles (which are usually easily found in the lighting shop in the Gnomish Town), the Bell of Opening (from the Quest), the Candelabrum of Invocation (which Vlad the Impaler has), and the Book of the Dead (held by the Wizard of Yendor). If you are playing Slash'EM, you also need at least two of the Key of Law (held by Nightmare), the Key of Neutrality (held by the Beholder) and the Key of Chaos (held by Vecna). Assuming you already have 7 candles, the bell, and two aligned keys if you are playing Slash'EM, you can proceed through Gehennom. I usually work my way down through Gehennom, so you may want to change the order a bit if you are starting at the bottom and working your way up.
Most of Gehennom is not particularly threatening to a character with a full ascension kit, because it is hard for hordes of monsters to surround you in the mazes. There are, however, some points it's worth watching out for.
Once you kill the Wizard of Yendor, he will be after you periodically until you ascend. He will reappear, curse your stuff with malignant auras, and surround you with hordes of nasty monsters. Therefore, it's a good idea to do as much preparation as you can before killing him for the first time, so that you can move fast afterwards. Map out every level, and dig paths between the upstairs and downstairs. Having speed boots and being unburdened will also help.
Usually the Wizard will remain in his tower until you approach him, but there is a small chance of him suddenly popping out to attack you. Some technical detail is required to explain this. The Wizard is created asleep and meditating, and will not leave his tower until both those states are removed. Many things can interrupt his sleep - for example the hell hound in his tower could step on a squeaky board. Fortunately, only a few things can interrupt his meditation from outside his tower:
Somewhere prior to the Wizard's Tower, there is a second set of up-stairs which leads to Vlad's Tower. Vlad is at the top of this three-story structure. Kill him and get the Candelabrum. Now, proceed down. You'll find three levels with a large rectangular area in the centre which cannot be entered by any means. These are the ``Wizard levels''. Below, there are two more levels with water-surrounded towers in their centres. One of these levels will have a magic portal to the Wizard levels in it. DO NOT ATTACK THE WIZARD YET! Finish mapping out all the levels until you find the bottom of the dungeon. You can find a complete list of the special levels you'll see in Gehennom at Dylan O'Donnell's Nethack Gazetteer if you play vanilla Nethack, or at my chart of the Slash'EM dungeons if you play Slash'EM.
On this bottom level is a vibrating square. To find it you must walk over it (at which point you will feel a strange vibration under your feet). Mark this spot somehow (leaving an object on it is a standard approach) and then make sure you have everything you need. Once you kill the Wizard of Yendor, you don't want to be wasting a lot of time looking for things in the dungeon. You should at this point have the Bell, the Candelabrum, and the seven candles, and you should know the location of the up-stairs on every level. Now, go back to the magic portal, enter the wizard's tower, climb the ladders until you reach the top level, kill the wizard and get the book. Now go back down (preferably by level teleport) to the bottom of Gehennom and go to the vibrating square. Make sure that Book, Bell, and Candelabrum are all uncursed (the candles may be cursed) and then apply the candles to the candelabrum, apply the candelabrum to light it, apply the bell, and read the book. A stairway down and a moat should appear if all goes well. You can now drop the Candelabrum, Bell, and Book: you won't need them any more, and the score bonus for ascending with them has been reduced in Nethack 3.4.0. Proceed down the stairs.
On the left of this level is a rectangular room which contains Moloch's high altar. Find the secret door (note that the room is surrounded by fire traps) to enter, kill the high priest of Moloch and get the Amulet of Yendor. As soon as you get it, name it something (for example ``REAL'') so that if the Wizard steals it, you'll be able to distinguish it from the fake Amulet he may have. The simplest way to assure yourself that you have the real Amulet is to try to put it into a bag. If it cannot be confined in such trappings, it's real.
Now, climb up the stairs (you can no longer level teleport while you have the Amulet). Note that in vanilla Nethack, while in Gehennom, you will sometimes randomly teleport down a few levels, when you are trying to go up a staircase. This effect is less severe for chaotic characters, but I wouldn't advise wearing a helm of opposite alignment to become chaotic, because you will lose all your protection if you do. In Slash'EM, this ``mysterious force'' has been removed, but you cannot teleport while carrying the Amulet.
Once you have the Amulet, keep moving towards ascension as fast as you can, to minimise the Wizard's chances to harass you. When he appears, it's a good idea to insta-kill him (wand of death, spell of finger of death, cockatrice corpse, cockatrice egg) so that he can't steal the Amulet, double trouble you or summon pets against you. When you ``feel a malignant aura surround you'', check your inventory to see what has become unblessed or cursed. If you rebless your bag of holding whenever it becomes uncursed, it won't become cursed and too heavy to carry around. (If it does become cursed, zap it with a wand of cancellation to uncurse it.)
Once you reach level one, stop and take stock before entering the Elemental Planes, because once you leave the dungeon, there's no going back. Here is my pre-Planes checklist:
Each of the Elemental Planes has a magic portal to the next plane. The easiest way to find these portals is to read a noncursed scroll of gold detection while confused. You can also use a crystal ball and search for ^. If all else fails, you can wear the Amulet of Yendor which will periodically provide clues to indicate how close you are to the portal. (Using cursed scrolls of gold detection is not advisable, because the portal will show up as gold, and will disappear when you see that there is no gold there.)
Dylan O'Donnell's Nethack Gazetteer has maps of the Planes. Here are some brief notes on what to expect on each plane:
Once you've passed through all four elemental planes, you'll reach the astral plane, and unless you're causing conflict, you'll almost certainly be given a guardian angel. Apart from the hordes of monsters, the main hazards here are the Riders or Horsemen of the Apocalypse (Death, Famine and Pestilence - by this stage you have become War incarnate). As of Nethack 3.3.1, you can no longer teleport away the Riders or their corpses; if you try, they will be revived and teleported next to you. Fortunately, Famine and Pestilence are vulnerable to wands of death. Death is not, so you just have to defeat him in combat, while keeping an eye on your hit points.
There are three altars on the Astral Plane, one of each alignment. Wade through the hordes of monsters (teleporting them out of your way will help), and find the altar to your god (you have to walk up to the altar to see which is which). Offer the Amulet of Yendor, and you'll be rewarded with the status of demigod(dess).