Procedural doesn't mean random, just generated from a set of rules. These rules can have inputs that lead to different results and you get randomness by randomising those inputs.

What's Intresting is this this exactly how most random number generators work because computers can't be random. They take a "seed" value and will always produce the same list of "random" numbers for a given seed. This means you can randomise all kinds of numbers in your procedural generation code but always get the same output if you give the random number generator the same seed.

So in No Man's Sky, for example, each planet basically has a set seed so the game will generate the same planet, on the fly, for everyone one who visits it in game. Which is why them tooting their own horn about having a whole galaxy to explore was a bit of red flag. All it meant was they generated a massive list of seeds which would have results limited by the tooling next to none of which they'd have been able to review etc.

Which is a long winded way of saying they'll basically create the world using procedural tools and save the inputs used so the game can generate the same fixed map for everyone that plays with out having to store/load a world's worth of data.