As stated above the shapes in the game are often strange and in real life the effects of gravity would probably cause Mario to fall all over himself. In the game however, he always comes out a hero by landing on his feet and in general looking really slick as he traverses the strange surfaces, such as the one below.
Calculating real gravity on a surface like this would be a task best left to Stephen Hawking. However, for the game to play correctly, the developers merely had to cast a ray relatively down from Mario's local center and grab the nearest surface normal.
Inside any 3D game engine worth its salt, there is a list of all polygons being rendered on screen and we can retrieve the first polygon that our ray cast intersects.
That polygon in this case represents our plane and the inverse of its surface normal represents the direction of gravity that will pull Mario smoothly back to the planetoids surface. That polygon's surface normal is also used to align Mario to the curvature of the planetoid.
In the illustration above we can see that the character is aligned to the surface normal of the previously jumped on polygon but the ray cast (dotted line) now intersects another polygon as the player crosses the border from one polygon to the next. In Galaxy, Mario's orientation is adjusted extremely smoothly due to a combination of factors.
First and easiest to understand is that each planetoid in the game is fairly high polygon so the change from one surface normal to another isn't too steep. Additionally, interpolation can be used to smoothly transition from one orientation to the next. So, the surface normals in a Galaxy planetoid are analogous to the key frames of an animation in that regard.
To demonstrate these concepts we'll be looking at some high-level source code we've created - written in Blitz3D, which is an excellent tool for prototyping concepts just like this. You'll need to download a demo or full version of Blitz3D to edit and re-compile the code.
Here's the specially created executable/source code package for Gamasutra readers to try that demonstrates a lot of the concepts used in Galaxy. The source code does a number of things including setup, camera tethering, and rendering.