The safest general characterization of the modern console gaming tradition is that it consists of a series of footnotes to Super Mario Bros. Of the dozen or so games to invent radically new possibilities for game space, three have had the phrase "Super Mario" in their name. Super Mario Galaxy will be the fourth.
Tevis Thompson's "close playing" of the original Super Mario Bros., "But Our Princess Is in Another Castle," got it right: Mario games are about jumping. That's the essential fun of playing Mario; jumping into and onto things, and especially squashing them. The Mario series is essentially a sequence of brilliant re-imaginings of how to embed Mario's jump into a spatial arena:
The original Super Mario Bros. was a side-scrolling platform game, with warp pipes and destroyable bricks providing a nonlinear topography for exploration.
Super Mario Bros. 3 extended this platforming in a second dimension: vertically, I hadn't thought it technically possible until I saw it. Mario's jump was now the launching point for a soaring, swooping flight.
Super Mario 64 again did the impossible: created a three-dimensioal platformer. The camera controls, the level design, and the overlapping sets of quests would all become models for many other games.
Super Mario Galaxy does something not just seemingly impossible, but previously almost unimaginable: puts Mario in space. He jumps from one tiny planetoid to another, in many cases running all around them: even upside-down, his feet firmly pointed inwards. Jump high enough, and he falls into a different planet's gravity well, flipping the right way as he drops. It's exhilarating, and the initial disorientation wears off within a few minutes. After that, you're jumping, slinging, sailing, and shooting from star to star.
Everything else is what you'd expect from a modern Mario game. Mario has to collect a bunch of stars, defeat a bunch of mini-bosses (mainly by jumping at just the right place and time, of course), and rescue the princess. There are hidden levels, cute enemies, and a difficulty level that ramps up from mild through insane (for those diehards aiming for 100% completion).
Nintendo's Yoshiaki Koizumi has discussed the development process for Super Mario Galaxy, and I'm not surprised that the hardest work involved thinking about how to make this new geometry work. They spent lots of time testing and refining the camera so it always shows a view that makes sense; they poured their hearts into crafting level segments that would take advantage of the news setting and the flexibility they had to create new gravities and shapes.
Some of my personal favorites:
Sections in which the direction of gravity regularly shifts by 90 or 180 degrees. Mario must make sure he's positioned near what's about to be a floor, even if it isn't one right now.
Spherical underwater levels, in which Mario must swim around inside a floating fishbowl.
Odd-shaped planetoids: toruses, corkscrews, conjoined cubes, and convex oddities. Every single one feels completely seamless.
Boss fights on spheres that involve projecting trajectories along great circles.
The game itself is good solid fun, but the vision behind it is inspiring.