Altars to Moloch can be found in the Valley of the Dead, in Orcish Town, in Orcus's lair, in the Sanctum, and in the Monk and Priest Quests; but they are marked as unaligned, and Moloch has nothing encouraging to say to you. Unaligned altars in Quests and Minetown can be converted; those in Gehennom cannot, and Bad Things will happen if you try.
Moloch makes his home in Gehennom, so any prayers there go to him instead of to your own god. This is a Bad Idea™, since your god doesn't like people who like Moloch, and Moloch just plain doesn't like anyone. Lightning and wide-angle disintegration beams ahoy.
The introduction text:
It is written in the book of (god X): After the creation, the cruel god Moloch rebelled against the authority of Marduk the Creator. Moloch stole from Marduk the most powerful of all the artifacts of the gods, the Amulet of Yendor, and he hid it in the dark cavities of Gehennom, the Under World, where he now lurks, and bides his time. Your god (god X) seeks to possess the Amulet, and with it to gain deserved ascendance over other gods. You, a newly trained (title X), have been heralded from birth as the instrument of (god X). You are destined to recover the Amulet to your deity, or die in the attempt. Your hour of destiny has come. For the sake of us all: Go bravely with (god X)!
Moloch (also spelled Molech) may have been an ancient Near Eastern deity. He is known exclusively from references in the Jewish and Christian Bible, but the name is probably related to a Hebrew word for "king" and so may be a title for another god. Some translators think he may have been the same as Milcom / Malkam, mentioned in the Bible as the national god of the Ammonites (living near present-day Jordan), whose name probably comes from the same root.
Within the Bible, Moloch's name usually occurs in phrases referring to 'giving one's seed to Moloch' or making one's children 'pass through the fire to Moloch', which has traditionally been interpreted to mean that Moloch was a god who was served with human sacrifices. These acts are said to have taken place at a site called Tophet, in the Valley of Hinnom, the Greek name for which was Gehennom.
Moloch's connection to human sacrifice, and even the reading of the word "moloch" as a proper name, has been questioned; nevertheless, in historical and contemporary media the name has come to be closely associated with human sacrifice, and is sometimes used as a metaphor for anyone or anything demanding extreme sacrifices.
The image of Moloch as a demon-god comes from a tradition within Christianity of reinterpreting the foreign gods of the Bible as demons posing as deities to mislead their worshippers. Christian authors like John Milton (in Paradise Lost) typically envisioned Moloch as a high-ranking fallen angel, on the basis of the meaning of his name ("king"), and assumptions about the extreme nature of his worship. This is probably why Moloch was chosen as the arch-fiend of NetHack.
And the Lord spake unto Moses, saying,
Again, thou shalt say to the children of Israel, Whosoever
he be of the children of Israel, or of the strangers that
sojourn in Israel, that giveth any of his seed unto Molech;
he shall surely be put to death: the people of the land shall
stone him with stones.
And I will set my face against that man, and will cut him off
from among his people; because he hath given of his seed unto
Molech, to defile my sanctuary, and to profane my holy name.
And if the people of the land do any ways hide their eyes
from the man, when he giveth of his seed unto Molech, and kill
Then I will set my face against that man, and against his
family, and will cut him off, and all that go a whoring after
him, to commit whoredom with Molech, from among their people.