The map is randomly generated like you say, and actually uses the map data part of memory. But instead of a 128 X 64 sprite area, it uses wraparound so it’s treated as a 16 X 512 area. So there is actually a finite depth, but most people stop playing before then. Then the entire map can just stay in memory without having to do anything fancy to make it go on forever (that would be pretty cool though. If I revisit this, I think I would take away the ability to fly back up to make this happen).
Here’s the source code if you’re interested. The relevant functions are mymset, mymget, randomizeGround, and drawGround
https://github.com/CaterpillarGames/pico8-games/blob/master/carts/binary-minery/binary-minery.p8