Altars to Moloch can be found in the Valley of the Dead, 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 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 Thing(tm), 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)!
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.