As Jagerbomber says, procedural doesn't mean random. More specifically, the pseudo-random number generator used doesn't depend in any way on any real random value (such as the current time or anything derived from it). Technically, it's not a RNG being used, but a random-number permutator, that computes pseudo-random value from existing stable values of the world.
So for example, tree placement is computed via random permutation from the coordinates of tree cell, plus some seed from parent terrain tile.