In module B2 (among others), a handy-dandy list of rumors is presented, so the players can get some leads to follow when they go off adventuring. This is a little trickier given the background I've come up with for my megadungeon. Since it hasn't been accessible for the past 3,000 years, there's no rumors to be had (well, there is one rumor that the Church of Starry Wisdom has been desperately clinging to, but they won't be sharing it with the party).
I'm going to initially handle this problem by letting the players find fragments of research and exploration notes from the original megacorporation foray into the dungeon. The research notes will be very brief, as I don't plan to sit at the table and orate a pages-long monograph on megadungeon exploration. I'm planning a sentence of background, to let the players in on some of the megadungeon history, and a sentence of rumor, to let them know what might be found in the deeper levels. This will give them some goals, so they aren't feeling completely aimless as they wander around. It will also let them know that getting to the deeper levels may be interesting, as I haven't told them that this is a megadungeon. That's something they are going to have to find out on their own.
An example would be, "...authorized construction of an on-site subsurface lab. They're also interested in getting more samples from the pool in B-level, after the test subjects' tumors..."
As the players go deeper, time will pass, and wizards, surface monsters, rival adventuring parties, and the city guard from the "friendly" city-state of Denethix will begin exploring the megadungeon through its alternate entrances. At that point, I'll have a plausible source for a random-rumors table, and I'll start dropping hints true and false at the local taverns.
The megacorporation responsible for the construction of the gatehouse, and the subsequent sealing off of the megadungeon, named the place the "Anomalous Subsurface Environment." It's a fairly bland name, for a place that defied known physical laws and promised untold riches to its explorers.
Probably the "Jackpot we're all rich if we don't die horribly Caves" name was already taken. JWARIWDDHC isn't quite as nice an acronym as ASE, either.