(Terminology: we say that a $k$-coloring of a graph $\Gamma$ is proper if adjacent vertices get different colors; two $k$-colorings are isomorphic if there is an automorphism of $\Gamma$ which takes one coloring to the other.)
Burnside's lemma
$$
|X/G| = \frac1{|G|} \sum_{g\in G}|X^g|
$$
applies to counting the number of orbits of any set $X$ acted on by a group $G$; it can already be used to count proper colorings. If $G$ is a group acting on a graph $\Gamma$, if we want $|X/G|$ to be the number of non-isomorphic proper colorings of $\Gamma$, just take $X$ to be the set of proper colorings of $\Gamma$ (counted by the chromatic polynomial evaluated at $k$.) The trick, however, is to evaluate $|X^g|$: the number of proper colorings fixed by a group element $g$.
Given a graph $\Gamma$ and a group element $g$ which permutes the vertices of $\Gamma$, a coloring is fixed by $g$ if, for every vertex $v$, the colors of $v, gv, g^2v, \dots$ are all the same. The way to compute $|X^g|$ in this case is as follows:
- If there is any vertex $v$ which is adjacent to $g^k v$ for any power $k$, then $|X^g| =0$, because there is no proper coloring in which $v$ and $g^k v$ are given the same color.
- Otherwise, we can define a smaller graph $\Gamma/g$ by taking a quotient: for every vertex $v$, identify $v$ with $gv$. (To enforce that these vertices get the same color, just make them the same vertex!) Then the number of proper $k$-colorings of $\Gamma$ fixed by $g$ is equal to the number of proper $k$-colorings of $\Gamma/g$, which can be found by computing its chromatic polynomial.
For a simple example, suppose we want to count the non-isomorphic $k$-colorings of the graph below:
a
/ \
/ \
b ----- c
\ /
\ /
d
The automorphism group has four elements: the identity $e$, the horizontal flip $h$ (which swaps $b$ and $c$), the vertical flip $v$ (which swaps $a$ and $d$), and their product $hv$.
The number of proper $k$-colorings fixed by $e$ is just the chromatic polynomial of the graph: $k(k-1)(k-2)^2$.
The number of proper $k$-colorings fixed by $h$ is $0$: if a coloring is fixed by $h$, then $b$ and $c$ get the same color, so it is not proper. Similarly, the number of proper $k$-colorings fixed by $hv$ is $0$.
For the number of proper $k$-colorings fixed by $v$, we want to take the graph quotient where we identify vertices $a$ and $d$ (since they must get the same color). This gives us the graph
ad
/ \
/ \
b ------ c
whose chromatic polynomial is $k(k-1)(k-2)$.
Now Burnside's lemma tells us that the number of non-isomorphic proper $k$-colorings is
$$
\frac14(k(k-1)(k-2)^2 + k(k-1)(k-2)).
$$