I use Jason Bevins libnoise library to procedurally generate planetoid meshes.
For the mesh generation I chose the simplest approach, a spherical object that is modified by the noise. I adapted the manual sphere mesh example from the ogre wiki. I only had to change it to have varying radii and calculate better normals.
Currently I am experimenting with the various libnoise modules and how to best use them. For example, I use the Ridged Multi module to get such chiselled objects. The standard Perlin noise module is used for more rounded objects. There are many parameters in libnoise which can be used to create more and more bizarre forms. With a little experimentation I also found how to create small moons (which I want to be of spherical shape and with very large craters or parts completely blown away by collisions).
(Click on the pictures for the full