You're going to tile (say) the plane with a set of tiles you've chosen beforehand. (In this example, it looks like the tiles are 3d.) There are rules for which tiles can go next to each other---the edges must match.
As you go, there are two regions: a region in which you've settled on which tiles to use, and a boundary region in which you haven't. In the boundary region, you keep track of a probability distribution over the tiles. This distribution is influenced by the neighboring tiles (exactly how is probably the most interesting bit of the algorithm; I don't know).
The algorithm proceeds by repeatedly (i) picking a tile on the boundary that has a very skewed probability distribution, and fixing it to be the most likely tile; and (ii) updating the probability distributions of the neighboring tiles in the boundary.
It's possible that you end up making poor tile placements at the beginning that gets you stuck later, so the algorithm must sometimes backtrack to undo past decisions. You want to pick a set of tiles such that the algorithm doesn't need to backtrack too often, or it will take too long.
Note that the distribution is an ordinary probability distribution, not a sum of complex amplitudes like the name "Wave Function Collapse" would make you think.