One way to generate a terrain heightmap is to generate a number of random hemisphere shaped hills with random radius on random coordinates and blend the them all together. By setting a min and max radius the final look can be tweaked to something you like. The result might look like the following:

Link to more detail about the algorithm (also the source for the image):
http://www.robot-frog.com/3d/hills/hill.html