The first step involves creating the basic geometry for the cave. Create a Plane (sized 1000) and set the Width and Length to 75 each. Right-click on the Plane object, and select Convert to: -> Convert to Editable Mesh. Now you have your editable mesh (you can extrude, bevel, move vertices, etc.), so go into Sub-Object Mode: Polygon (Hotkey 4 on your keyboard). Select any of the polygons that will make up the base of your cave walls (don't worry about jagged edges for now). Now hit click in the box next to extrude, and type in 100. Click outside of the box to activate the extrusion. Extrude the same way again, except with 50 this time.
Now you have your base mesh... doesn't look like much of a cave, does it? We'll fix that up.
Go into the Modifiers tab, scroll down to Parametric Deformers, then click Noise in its sub-menu. Enter in some random values for distortion on axes similar to my values. The purpose of this is to rough up the mesh a bit, and make it look less perfect.
Obviously this mesh is still very jagged and wouldn't be good at all for a smooth cave.
So... go back into the Parametric Deformers sub-menu (same place you found Noise), and choose the Relax modifier. This will get rid of hard edges on your object, making it look more smooth. Set your Relax value to 1 since those walls are VERY jagged, and set your Iterations at 5 or greater depending on how you want it to look.
It's a bit smoother now, but still seems slightly jagged in some places. So if you feel inclined, add a Meshsmooth or Smooth (check Auto-smooth) modifier. I'll note here that you'll probably want to add a Meshsmooth LAST before rendering since having all those polygons will slow up your viewport rate significantly, making everything hard to work in.
That's pretty much it for the cave mesh. If you feel like it, you can take some personal control and move vertices, edges, and whatnot, but that's up to you.
Texturing the cave! Coming soon...
