It's based on Burnside's lemma.
The rotation group $G$ of the necklace is a cyclic group of order $n$. Let $\alpha$ be a generator of $G$, i.e. a rotation of order $n$, such as the rotation by one bead in the positive direction. Thus $G=\{\alpha^1,\alpha^2,\dots,\alpha^n\}$ where of course $\alpha^n$ is the identity permutation.
For $k\in\{1,2,\dots,n\}$, the rotation $\alpha^k$ is a permutation of order $\frac n{(k,\,n)}$ where $(k,\,n)$ is the greatest common divisor of $k$ and $n$; it partitions the set of $n$ beads into $(k,\,n)$ orbits, each of size $\frac n{(k,\,n)}$.
A coloring is invariant under $\alpha^k$ if and only if it's constant on each orbit; thus, with $2$ colors, the number of invariant colorings for $\alpha^k$ is $2^{(k,\,n)}$. According to Burnside's lemma, the number of indistinguishable colorings is obtained by averaging the number of invariant colorings over all elements of the group; thus
$$Z_n=\frac1n\sum_{k=1}^n2^{(k,\,n)}.$$
All that remains is to verify that
$$\sum_{k=1}^n2^{(k,\,n)}=\sum_{d|n}\phi(d)2^{n/d}.$$
This is true because
$$\phi(d)=|\{k\in\{1,\dots,n\}:(k,\,n)=\frac nd\}|$$
or, equivalently,
$$\phi(\frac nd)=|\{k\in\{1,\dots,n\}:(k,\,n)=d\}|.$$
For an arbitrary number $c$ of colors, just replace $2$ with $c$ in all the formulas; the number of indistinguishable colorings is
$$\frac1n\sum_{d|n}\phi(d)c^{n/d}.$$
When $c=1$ this reduces to the familiar identity
$$\sum_{d|n}\phi(d)=n.$$
You are correct, you want to use Burnside's lemma:
$$\mbox{# of Orbits}=\frac{1}{|G|}\sum_{g\in G}|fix(g)|.$$
You have an action of $G=D_{2m}$ on the set $X$ of $n$-colored necklaces with $m$ beads, and two such necklaces are the same if they are in the same orbit under this action. Therefore, counting the number of orbits counts the number of necklaces.
Let's set up some notation. We can regard a necklace as a regular $n$-gon with vertices numbered $\{1,\ldots,m\}$. Then, $G$ act on the vertices in the natural way. This corresponds to an embedding $G\hookrightarrow S_m$. Identifying an element $g\in G$ with its image in $S_m$, let $\psi(g)$ denote the number of disjoint cycles in the cycle decomposition of $g$.
Let $C$ be a set of $n$ colors (i.e. $|C|=n$). Then $G$ acts on $X=C^m$ by $$g.(c_1,\ldots,c_m)=(c_{g.1},\ldots,c_{g.m}).$$
Lemma: For the action of $G$ on $X$, we have $|fix(g)|=n^{\psi(g)}$.
proof: Since, for all $k$, $g^k.(c_1,\ldots,c_m)=(c_{g^k.1},\ldots,c_{g^k.m})$ we see that $(c_1,\ldots,c_m)$ is in $fix(g)$ if, and only if $c_i=c_{g^k.i}$ for all $i$ and $k$. This just says that $(c_1,\ldots,c_m)\in fix(g)$ if, and only if the coloring is constant on the cycles of $g$. There are $n$ choices to color each cycle, leading to $n^{\psi(g)}$ total colorings that are fixed by $g$.
Example: Suppose $m=4$ and $n=3$. The element of $D_8$ and their cycles types are chosen as follows:
$$
\begin{array}{llll}
1=(1)(2)(3)(4)&r=(1234)
&r^2=(13)(24)&r^3=(4321)\\
j=(24)(1)(3)&rj=(12)(34)&r^2j=(13)(2)(4)&r^3j=(14)(23)
\end{array}
$$
The corresponding orders of $fix(g)$ are given by
$$
\begin{array}{llll}
n^4&n&n^2&n\\
n^3&n^2&n^3&n^2
\end{array}
$$
Therefore, the number of necklaces with $n$ colors is
$$\frac{1}{8}(n^4+2n^3+3n^2+2n).$$
Substituting $n=3$ yields $21$ distinct necklaces.
Best Answer
Basically you have to find out which necklaces are identical. Necklaces are identical if they are identical under symmetric operations just as rotate them ($r$) or turning them around ($s$).
First of all I explain why you get the powers of 3.
Look at the case that you do not turn the necklace (you apply the identity $\{e\}$). Because all of 9 beads can have different colors, you can have $3^9$ different necklaces.
Now look at what happen if you consider the rotation $r$, that means you rotate the necklace $2 \pi / 9$ around. If you do so until you reach the point where you began you will see that the necklace stays only identical for all $r, r^2, r^3,..., r^8$ if all the breads have an identical colour, so there are 3 options to create such a necklace.
Now turn the necklace upside down. There is 1 bead that is fixed and all the other 8 beads are at a new position. For the necklace to be identical under this symmetric operation (call it $s$) the 8 beads that change their position have to have the same colour as the bread that was at this position at the beginning. Because of this you have 5 breads where you can choose the colour and then the remaining four must have fixed colours. This corresponds to $3^5$.
Now look at the case if you rotate the necklace around $2 \pi / 3$ corresponding to $r^3$. Then you can choose the colour of three breads and through rotation the other 6 breads must have colours depending on the colours of the first 3. Hence you have $3^3$ choices for the colours.
Take a look at the conjugacy classes of the symmetric operations.
The case $3^9$ corresponds to the identity {e} from which there is one. The rotation $r$ could aswell be $\{r, r^2, r^4, r^5, r^7, r^8\}$ because all the elements are of order 9, which means that they bring the necklace back in the starting position after 9 times applied. Notice that this are 6 elements, so its 6 times 3.
$\{r^3, r^6\}$ form another conjugacy class, so you have $2 \cdot 3^3$.
The last conjugacy class is $\{s, rs, r^2s, r^3s, r^4s, ..., r^8s\}$ containing 9 elements, thus $9 \cdot 3^5$.
At last, notice that $|G| = 18$ because we have 18 possible symmetric operations here: $\{e, r, r^2, ..., r^8, s, rs, r^2s, ... r^8s\}$.
Maybe you can try the case of 6 breads of 3 different colours yourself now and ask if you get stuck anywhere.