Putting it differently: the basic steps of the Markov chain are "hexagon-moves" on the tiling, where one executes a non-trivial hexagon-move by changing the way a small unit hexagon of side-length 1 inside the large region is tiled by three rhombuses (there are exactly two ways such a hexagon can be tiled).
Comment by the author, January 16, 1998: Section 3 specifies that one is to choose the successive randomization sites x from the uniform distribution on P (or more generally from any probability distribution that assigns positive probability to each element of P). However, one has a great deal of leeway here. For instance, one can use a deterministic sequence of x's that cycles through the set of elements of P; as long as the coins used in the algorithm are random, the procedure will still lead to a random order ideal. In the case where P is ranked, one particularly natural idea is to do all the x's of even rank, followed by all the x's of odd rank, and so on, in alternation. This particular scheme is well-suited to parallel computation, since all the randomizations of the same parity that are considered in any cycle can be done independently of one another.
Comment by the author, July 17, 1998: An algorithm developed by Christian Kratthenthaler gives one a very different way to generate random lozenge tilings of a hexagon. See his preprint "Another involution principle-free bijective proof of Stanley's hook-content formula". The bijective proof presented in the article can also serve as the basis of an algorithm for randomly generating Young tableaux of a given shape with bounded entries. A suitable modification of the algorithm randomly generates plane partitions whose Young diagram fits inside a given box.