The answer is particularly nice for lozenge or domino tilings. There is a very elegant picture of "the space of tilings" of a certain region which makes the connection between height functions, max-flow-min-cut, the topology of the region and the respective Cayley graph very clear. I'm going to try to present the details here, but I'll also include some references in the end. It also helps a lot if you work out some examples by hand.
The main problem is, of course, being able to tell if a certain region can be tiled. If we restrict ourselves for a moment to simply connected regions, Conway-Lagarias gave a necessary condition which says that the word corresponding to the boundary should be the identity in the tiling group $G$. Let the Cayley graph of $G$ be $\Gamma$, which we can embedd as a lattice in $\mathbb R^3$ for lozenge or dominos. Now, the tilings themselves live in a plane region which is trianguated or quadriculated, and we can orient the edges of this triangulation/quadrangulation so it becomes $\Gamma_1$, the Cayley graph of $G_1$, which is a quotient of $G$ ($G_1$ is isomorphic to $\mathbb Z^2$ in both cases, but for lozenges we consider three generators, $(1,0),(0,1),(-1,-1)$). In both cases we can make the embeddings so that the projection $\mathbb R^3\to\mathbb R^2$ also projects $\Gamma\to \Gamma_1$.
Now a graph is a $1$-complex and once we introduce a tiling this turns the tiled region into a $2$-complex in the obvious way. This complex lifts up to translation to a unique surface in $\mathbb R^3$. Therefore tilings are in bijection with such surfaces up to translation. The height function for a tiling is just defined as the distance between a vertex of $\Gamma_1$ and the point on the surface which projects to it. Usually one fixes a point on the boundary to have height zero in order for the values at the other vertices to be well defined.
More concretely, for lozenges we have
$$G=\langle a,b,c \, | aba^{-1}b^{-1} = bcb^{-1}c^{-1} = cac^{-1}a^{-1} = 1 \rangle \simeq \mathbb Z^3,$$
so $\Gamma$ is just the cubic lattice with positive directions given by $(0,0,1),(0,1,0)(1,0,0)$. The projection is on the $x+y+z=0$ plane so that $\Gamma_1$ is the skeleton of the triangular lattice with the corresponding edge orientations. Tilings of a region will correspond to a surface on the cubic lattice with fixed boundary. Notice that the height function as defined above increases by a unit when crossing an edge in the positive direction (Cayley graphs are oriented) and decreases by a unit otherwise.
For dominoes the picture is slightly different because the tiling group
$$G=\langle a, b \, | a^2 b a^{-2}b^{-1}= b^2ab^{-2}a^{-1}=1 \rangle$$
is non-abelian. To embed it in $\mathbb R^3$ introduce a third generator $c=[a,b]$ so that
$$G=\langle a, b,c \, |ac=c^{-1}a,bc=c^{-1}b,ab=bac\rangle.$$
Now every element in $G$ is in bijection with a word $c^wb^ya^x$. We represent this word as a vertex in $\Gamma$ by the lattice point $(x,y,z)$ where $z=4w$ if $x$ and $y$ are even, $z=4w+1$ if $x$ is odd and $y$ is even, $z=4w-2$ if $x$ and $y$ are odd and $z=4w-1$ if $x$ is even $y$ is odd. The projection of $\Gamma$ on the plane $z=0$ gives a square grid, and the tilings lift to surfaces with a fixed boundary, therefore defining a unique height function up to translation. Again the height function can be described locally by the difference at neighbouring vertices which will depend on the orientation of the edges in $\Gamma$.
Now since we are talking about simply connected domains, we can prove something nice from this picture. We can define some local moves (generally called flips) which in the case of lozenges switch the "full box" diagram with the "empty box" diagram, and for dominoes they switch two parallel horizontal dominoes with two vertical ones. If we assign to such moves a $3$-cell, this turns the collection of tilings into a contractible $3$-complex and therefore we see that one can transform any tiling into any other one just by a sequence of local moves. In fact with a little more work one can show that tilings form a distributive lattice where the minimum of two tilings is given by the lower convex hull of the two corresponding surfaces.
Now, what remains is the question of what happens with non-simply connected regions, and what does max-flow-min-cut have to do with all this?
Well, first we want to be able to tell as quickly as possible if a region can be tiled. This is what Thurston's algorithm does, and if the answer is yes it gives the minimal tiling in the sense described above. For the algorithm check the references below. A brief description is that one starts by building a candidate height function for a minimal surface inductively, by specifying the boundary first, and then assigning values to interior vertices greedily. There will be no tiling possible if we meet an inconsistency along the way.
The max-flow-min-cut theorem provides a characterization of height functions on the boundary which extend to the entire region, while at the same time giving some insight as to how one might naturally discover Thurston's algorithm. A height function defines a flow on the dual graph of $\Gamma_1$, while a cut in this dual graph corresponds to a directed path in $\Gamma_1$ joining two vertices on the boundary. We can define $d(u,v)$ to be a non-symmetric distance function, measuring the length of the minimum directed path from $u$ to $v$ in $\Gamma_1$. Max-flow-min-cut for the dual graph can be rephrased into a statement characterizing valid height functions:
Theorem. Given a simply-connected region $R$ in the square lattice. There exists a tiling if and only if there is a function $h$ on the lattice points of $R$ which satisfies $h(u)-h(v)\le d(u,v)$ for all $u,v$ on the boundary.
This is also incidentally the condition under which Thurston's algorithm gives a positive answer. A similar statement will hold for lozenge tilings. A detailed discussion is given in this senior thesis of Matina Donaldson. All these statements have analogues for surfaces with arbitrary topology, but then one must consider height sections of a certain height bundle on the graph. Using the same techniques one can compute the number of connected components of the tiling space. For this general setting you can look at "Spaces of domino tilings" by Saldanha, Tomei, Casarin and Romualdo. The first two authors have another nice note "An overview of domino and lozenge tilings".
