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.