Lava caves (also known as lava tubes) are formed by hot lava that flows out from a volcano.  The outer cover of the lava hardens.  Inside the lava is still flowing leaving a cave behind it.  The only way you can build onto a lava cave is if the same volcano erupts and the lava continues down the same path as the first lava flow.  Sometimes the lava knocks down the first cave destroying the lava tube.

Image courtesy of http://www.dgl.microsoft.com