A heightmap is probably the most efficient way to store the data, though you will have to worry about smoothing the terrain to avoid it looking like stair-steps.
look up fractal terrain generation and the roam algorithm. with fractal terrain generation you can generate a random terrain each time you play the game for example.