Step 1: Generate a map of solid rock. Use Perlin noise (or whatever) to make it of varying density.
Step 2: Place points of interest in the rock.
Step 3: Use a pathfinding algorithm to connect those points using the rock density as movement cost.
This will create a a map that is guaranteed to connect all the interesting points and the paths between them will wind, curve, connect, and split trying to follow the path of least density between the points. By varying the size of the path finder or removing low-density tiles near the path, the caves can be made to look more interesting.
Here's an example that connects 9 points on a map that is 120 by 40 tiles.
And here is a view that shows the density of the rock, the lighter it is the more dense it is and the less likely a cave will go through it.
There you go, caves that twist and wind and widen and narrow from point A to point B.
