It's enough to show that any edge can be rotated into one of the neighbouring edges; by composing such operations, you can move any edge to any other edge. To rotate an edge into a neighbouring edge, rotate through $2\pi/3$ about an axis through the vertex they share.
For an edge to be rotated into itself, the axis has to pass through the centre of the edge and the angle has to be $\pi$; this is the only kind of rotation that leaves a line segment invariant, other than a rotation about an axis along the line segment, which isn't an option in this case.
First off, forget the dihedral group and go right for the cyclic group $C_4$ (or $\Bbb Z_4$ if you prefer that). That removes one layer of abstraction.
We pick the group of rotations of the square, because that is the precise group of symmetries that we consider "not to change" the grid in our final answer. We want to consider grids that are rotations of one another to be the same, so the group of rotations is what we're going to look at. If we also considered mirrorings to produce "the same grid", then we would use the dihedral group $D_4$, since that is the group of "rotations and mirrorings".
Let $M$ be the set of the $m^{n^2}$ differently coloured grids (where we do consider rotated grids to be distinct; this is the easy one to count). Then each of the four elements of $C_4$ induces a bijection $M\to M$, intuitively given by rotations by $0^\circ, 90^\circ, 180^\circ$ and $270^\circ$ respectively. The product of elements in $C_4$ corresponds to compositions of rotations. This collection of bijections, and the correspondence between these two operations is called a $C_4$-group action on $M$.
Consider the equivalence relation $\sim$ on $M$ defined by $x\sim y$ iff one of these four bijections takes $x$ to $y$. Then the equivalence classes are called orbits of this action. We are after the number of such orbits.
The vast majority (at least for large $m$ and $n$) of these equivalence classes will have size $4$. So $\frac{m^{n^2}}{4}$ is a decent first approximation to the final answer. However, some will have size $2$ and some will have size $1$, and trying to count the number of orbits of each size directly is a pain.
That's where burnside's lemma comes in. Instead of focusing on the number of equivalence classes of each size, this lemma leverages the orbit-stabilizer theorem to change focus entirely. We now take each of the four bijections, and count the number grids that are mapped to themselves:
- For the $0^\circ$ rotation, that's $m^{n^2}$, as each grid is mapped to itself.
- For the $90^\circ$ rotation, that's going to depend on the parity of $n$. If $n$ is even, there are $m^{n^2/4}$ grids that are mapped to themselves by this rotation, while for odd $n$, the answer is $m^{(n^2 + 3)/4}$.
- For the $180^\circ$ rotation, and even $n$, there are $m^{n^2/2}$ grids that are sent to themselves, while for odd $n$ there are $m^{(n^2+1)/2}$ grids.
- For the $270^\circ$, the answer is the same as for the $90^\circ$
Now just take the average of these four numbers (in each case picking the right one depending on whether $n$ is even or odd), and you get the number of orbits.
Best Answer
To define a group action, you need:
1) A group $G$ (In you case, $G = D_4$ is fixed.)
2) A set $X$ (you gave several suggestions, like the set of vertices of a square).
3) A multiplication rule $G\times X \to X$ satisfying the axioms of a group action.
In your suggestions, I'm missing 3).