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.
Best Answer
This problem is well-known in combinatorics, you can look for example here: https://en.wikipedia.org/wiki/Necklace_(combinatorics)
The number of necklaces with $m$ beads and $n$ colors is $\frac{1}{m}\sum_{d|m}\phi(m/d)n^d$, where the sum is over all $d$ dividing $m$, and $\phi $ is Euler's totient function. When $m=p$ is a prime the sum has only two terms and it simplifies to $\frac{1}{p}(n^p+n p-n)$