To make such a landscape, one basically subdivides a square into four smaller equal squares, and then vertically offsets their shared center point by some random amount. The process is repeated on the four squares in turn, and so on, until the desired level of detail is reached. Since there are many fractal procedures (such as Perlin noise) capable of creating terrain data, however, the term "fractal landscape" has become more generic.
Kenton Musgrave is considered a leading authority on fractal landscapes and his most recent computer program, MojoWorld, is one of the more convenient ways to investigate them. The core of Dr. Musgrave's work in this area centered on rendering planetary bodies from orbital heights smoothly down to the surface with adapative level of detail. Mojoworld basically makes this process interactive for anyone with a sufficiently powerful PC. Another highly popular program in this vein is Matt Fairclough's Terragen.
Although fractal landscapes look natural at first glance, repeated exposure brings disappointment to those who expect eroded mountains. The main complaint is that simple fractal processes do not (and perhaps cannot) mimic actual geological and weathering functions.