Bzroom summed up the iterative process of creating a level or map fairly well. As an environment artist I can say that making levels is a cooperative endeavor that involves multiple disciplines and usually requires compartmentalizing tasks.
A game like Super Mario Galaxy may appear complex to someone who is approaching it from a paper design perspective. Sketches would be key to figuring out the type of game play and visual presentation that the designers hope to achieve. Orthographic paper concepts aren't the best solution for a very 3d spatial-centric game. Commonly 3d whiteboards are used now to present the layout of a level, which essentially are extremely simplified 3d spaces.
Once the overall concept and story for the game has been identified some concept artists would be able to create some basic concepts to drive the aesthetic of the levels, planets, maps, or whatever you want to call the play space in your game. At that point designers would be able to plan what types of navigation, enemy encountes, puzzles, and events they would like to introduce in each level.
Mission/level objectives and pacing would be largely determined by designers and writers if applicable. From there, playable levels could be created in primitive 3d form. From these primitive forms the concept artist could further refine the look and details of the environments. The concepts would then get passed back to the environment artists to refine and finish the spaces. Of course the level is undergoing several iterations of change as required by design based on their goals and play test feedback. As already stated, it's a very organic process and the level can go back and forth between these different stages several times.
Since I work on FPS games the level design process that I go through is much more sophisticated than what I just described for a 3d platformer such as Super Mario Galaxy. Many of the phases remain the same, but include additional tasks that don't seem so obvious at first.
In a nutshell:
Overall Game Concept -> Story/Setting -> Mission Concepts -> Environment Aesthetics Concepts -> Cinematic Requirements -> 3d Whiteboard/Layouts -> Level Concepts -> Mass-out (playable prototype at the end of this phase) -> Design Input/Revisions -> Key Environment Concepts (Primary Views/Unique Sections) -> Architecting -> Play Test Feedback -> Design Iteration -> Production Concepts -> Environment Finishing Work -> Bug Bashing -> Design Iteration/Environment Rework as necessary -> Polish -> More Testing -> Fix and Done!
It's not always as linear as this, but this should illustrate the point that a level goes through several stages and in each stage there are usually several iterations of development. This also requires the cooperation of several different disciplines from game designers, writers, cinematic artists, concept artists, level designers, environment artists, and testers.
Since the terminology usually varies between studios I'll try to explain some of the less obvious tasks.
Mass-out is the phase where the level is created in simplistic 3d form at a level of detail greater than the 3d whiteboard. The goal here is to break the level into playable sections that will allow for proper resource management. In a complex 3d environment it's not possible for the CPU to draw the entire level or world at once so it's necessary to break the level into sections that can be occluded or unloaded from memory. This is less of a problem for top-down adventure games (Zelda, Diablo, etc.) and RTS games since the camera is typically fixed and only lets the player view a very small portion of the map at a time. In mass-out the environment artist and level designer figures out how different parts of the level will load and unload so that frame rate (performance) is consistent and playable throughout the entire level. Additionally, this helps the environement artist figure out what fidelity can be expected in lightmap resolution and vert count for each section of the level. The goal is to have a playable prototype of the level at the end of this phase.
Architecting is the phase where the environment artist begins to actually refine the simplistic 3d shapes created in mass-out. This is where we start adding ramps, bridges, railings, trees, rocks, tunnels, etc. At this point the designer starts setting up AI and basic scripts. A lot of iteration to the overall design occurs during this phase based on play testing feedback.
Environment Finishing Work is basically taking all of the simplified features created in architecting and completing them from an art standpoint. Typically, though finishing artists will get the visual level of all the assets in the level to about 95% complete at this phase since the final touches on art is done in polish.
Production Concepts are basically concepts that directly inform the environment artist what the final vision of a very specific part of the level will look like including all elements that may effect gameplay.
Key Environment Concepts are concepts that depict the primary views, scale, mood, lighting, etc for key parts of the level.
I think the rest of the phases are somewhat self-explanatory.