As far as I know midpoint displacement does not help with the caves ... there is an article with some more text: http://www.gameprogrammer.com/fractal.html
You will probably have to combine several algorithms to get the result you want.
Midpoint displacement can be used to create the base terrain ... then, for example, cellular automata to create caves inside that terrain!?
This is an art rather than a skill, meaning that learning to think the right way is more important than finding the right tutorial.
You should feed Google with those algorithms (http://pcg.wikidot.com/category-pcg-algorithms), pick the ones that inspire you and do simple things with them.
If you have a hard time coming up with a data structure and algorithms for populating a game world, maybe you should work on those basics some more ... for example with some Code Jam exercises.