At the heart of most methods for generating maps lie a layer of noise. The most famous noise generation algorithm is Perlin Noise. Algorithms like Perlin Noise offer pseudo-random results. You choose a random seed for the algorithm, and for the same seed, the algorithm will spit out the same results. For my map generation, I use a noise generation algorithm called Simplex Noise. A more in depth article which explains Simplex Noise fairly well is located here. It also contains Java source code!
Running the Simplex Noise algorithm might leave you with a result similar to what you see in the left image.
My goal with the noise is to end up with something I can use as a Heightmap. You can find plenty of example images on the web, and after looking at a couple, you'll probably agree with me that my result needs some refinement. Using something similar to what's called Fractional Brownian motion, I end up with a result similar to what you see in the right image. Now I'm getting somewhere.