It sounds like you're looking to generate a "side view" of the generated terrain.
There are plenty of terrain generation algorithms discussed on the web. You could probably adapt many of them by cutting out all but one dimension from the calculations. This would give you information about the primary surface/underground boundary. If you want to be more directed in your search, you probably want to look for "1D" terrain generation or "Worms-style" terrain generation. You'll get results like this thread on procedural terrain (including caves), and this interesting web demo.
Perlin noise alone would work well for the areas where you want to generate plains, since it's very smooth. It doesn't work so well for mountains and craggy areas with sharp discontinuities -- you'd want to combine it with something else for that. Consider the first portion of this page on fractal terrain, or applying random cuts and displacements to the terrain.
Caves can be done by randomly punching holes in your terrain as a simple first pass, but you can also look for information on how rooms in Rogue-like games are generated and apply that. You might also consider looking into cellular automata.