The megadungeon is a historical and exciting campaign model with a simple appeal that’s a convenient platform for pickup games, but building one can be an intimidating challenge. There are probably as many approaches to building the megadungeon as there are approaches to the megadungeon proper. Here is one such approach.
Step 1: Start with the “Swiss Cheese Assumption”
This assumes that the ground is full of natural caves, passages, burrows, etc… You don’t need this assumption to hold for your entire campaign world, it can be localized due to geologic (think lava tubes or limestone erosion), ecological (think prolific burrowing critters), or societal factors (think dwarves), but whatever the reason, this means that even caves and structures that were never intended to be part of a megadungeon are easily connected to it. Give some thought to what factors have led to the Swiss cheese assumption in your game. It will be important later.
Step 2: Overland design
Overland design has two major goals: adding variety and encouraging just the right amount of overland exploration. The first goal is easy. Simply choose a handful of different terrain types (using common sense) and array them aesthetically and reasonably about your starting area. This gives a variety of places for the PCs to explore and a variety of sources for monster and dungeon types. The second assumption is the more difficult one. You want that variety of terrain and you want your players to explore it. It gives them an additional secondary goal that can reward PCs with information about and paths into the megadungeon, but you also want to limit the amount of overland exploration to the relevant surrounding area. There’s no point to the PCs going on extended overland adventures to the next country over. That’s not what the megadungeon campaign is about. Discouraging extraneous overland exploration can be done in several ways. It can be done explicitly, by simply telling your players the limits of the area you’re interested in dealing with. It can be done by making the areas you’re NOT interested in boring (no monsters, no rewards, just endless farmland…) or it can be done by putting a clear demarcation between the area you’re interested in and those you’re not (for example you might place the megadungeon on an island or peninsula, or in a valley or some other barrier). Generally a mix of all three works best. Place your megadungeon in a clearly designated geographical area, and tell your players what you want to cover with the campaign and that nothing interesting is found outside that area (and thus that’s why the PCs are here).
Step 3: The town
The town is the base of PC operations in the megadungeon campaign. As such, some thought should be given to the goods and services available and to the relationship between the town and the megadungeon. Was the town built on top of the megadungeon by accident? Because there’s some resource of value that both the builders of the town and megadungeon wanted? Is the town just a collection of lean-tos put up by adventurers on their way to the megadungeon? Or maybe it’s an entrenched fort to keep the inhabitants of the megadungeon from ravaging the countryside?
Step 4: Realms
The first step in building the megadungeon itself should come in the form of Realms: large scale areas with an overarching theme or flavor. The first few of these should be based at least partially on your overland areas, and may extend above ground in the form of ruins, towers, etc… but others deeper in the earth can be completely divorced from the surface terrain. Some examples might include a dwarven city and mine, a natural cave system, an underground sea, a collection of geologically active magma tubes, or a crystal-rich cave system. These realms share common themes, flavors and encounter tables, although there’s definitely room for diversity within. Realms are where the Swiss cheese assumption comes in. With the ground littered with passages, it’s impossible for realms NOT to be interconnected, so even if they wouldn’t otherwise be connected, the assumption links up all your realms and any other minor dungeons in your campaign nicely.
Step 5: Zones
Within each realm, there are smaller areas we’ll call zones. These share at least partially the overarching theme and flavor of the realm but have their own twist. For example, our abandoned dwarven city realm might have the following zones: Barracks, Market district, prison, noble district, and palace. Though all are dwarven construction, maybe the prison contains incorporeal undead horrors spawned from the prisoners slow starvation after the city fell. Similarly, the palace might be full of other-planar entities and aberrations which pour through a rift in the wizard’s laboratory.
Step 6: Entrances
By this point you should have plenty of ideas how PCs get into the megadungeon. Some of these ideas are obvious. The dwarven city had an entrance in the mountains, the elven barrows has collapsed brickwork that leads to the natural cave system, etc… but others can be more fun to place and for players to discover. Maybe the town well is fed by an underground river that’s connected to the megadungeon. Multiple entrances, especially tricky ones reward players for exploration, problem solving and finding alternate routes in and out.
Step 7: Maps
At this point it’s time to start mapping. Some zones and even some realms don’t need maps. They might have some kind of skill check to navigate safely or could be “mapped” loosely. Other zones might be small, and need a map for 5-15 rooms. Others could be so large as to have sub-zones or be mega-dungeons in their own right.
Megadungeons are no longer the standard for campaigns, so they’re likely to be new to some newer players and sources of fond nostalgia for some older players. They lack certain more modern aspects that have come to dominate the RPG scene, such as overarching story (unless you consider “Go explore the dungeon because it’s there” and overarching story) or heavy role-playing opportunities, but instead they offer a simpler game experience and provide an easy platform for rotating player bases, pickup games and similar challenges while satisfying the itchy swordarms of the grognard in all of us.
I’m hardly the only one writing about megadungeons. Here are some links to further reading that will be of value in setting up your own dungeons:
Angry Dm’s Project Slaughterhouse 
Alexandrian’s Jacquaying the Dungeon 
Simon C’s “How I draw dungeons”