In this method, you start with a flat landscape and repeatedly add or subtract height from some portion of the bitmap. Traditionally, you draw a straight line across the bitmap and raise the "land" on either the left or the right by one unit. Repeat this many (e.g. 1,000 - 10,000) times with randomly placed lines of random slope and you get some reasonably attractive mountains. This approach was used by Voss and Mandelbrot in building early fractal landscapes. This is generally an expensive approach, although there are some methods that can be used to speed it up in some cases. An example applet using this technique can be found here.
John Olssen has implemented a variation of this method in which cuts are made along great circles on a sphere.
Aki M Lumme recommends a similar method in which filled disks/circles of random radius are placed at random locations on the terrain. I think something similar is used for the cratering option in recent versions of gforge.
Instead of circles, rectangles can be used. These are easier to compute, and that may be more important for your application. Magnus Lindhe has written a Java applet that implements this technique, followed by a simple smoothing filter. Source code is available, check with Magnus for usage restrictions.
Cones may also be used instead of circles. These are basically circles, but the height increases toward the center of the circle instead of remaining constant.
A smoother function than cones is a crater function such as HF/(F+x^2+y^2). H is +/- distance moved at the center and F is a smoothness factor. A small F gives a very pointy mountain/depression and a large F gives a large smooth area.
A more complex function can be used, of course. John C. Gallant and Michael F. Hutchinson presented a paper in which they described landscape analysis using the positive wavelet decomposition. The "wavelet" shape they used was an elliptical hump (or depression, depending on sign). Although the inverse wavelet transform can't be used with this type of wavelet to generate a heightfield, the list of terrain features can be used to draw the heightfield bit by bit, just like with cones. This approach seems promising, but needs some additional work in order to be really useful for terrain synthesis.
John Olsson's Fractal Worldmap Generator
"Towards an Understanding of Landscape Scale and Structure"
Up to the terrain synthesis page
© 1996, 2011 cburke@mitre.org