Take for example the simplest action there is--the action of $S_n$ on the set $X=\{1,\cdots,n\}$ for which you just define $\sigma\cdot x=\sigma(x)$. Note then that an orbit $\mathcal{O}_x$ of $x\in X$ is just the set $\{\sigma(x):\sigma\in S_n\}$. But, of course $\left\{\sigma(x):\sigma\in S_n\right\}$ is just $X$! Any element of $X$ is hit by $\sigma(x)$ for some $\sigma$. Thus, since this was true for all $x$ we see that the number of orbits of this action is $1$ (they are all just $X$). So, $\#(X/S_n)=1$. Now, what is $X^\sigma$ for some $\sigma\in S_n$? By definition it's all the elements of $x$ for which $\sigma\cdot x=x$ or, in other words, $\sigma(x)=x$. So, in more combinatorial notation $X^\sigma=\text{Fix}(\sigma)$. Thus, the theorem that is not Burnside's tells us that
$$1=\#(X/S_n)=\frac{1}{|S_n|}\sum_{\sigma\in S_n}\#(X^\sigma)=\frac{1}{n!}\sum_{\sigma\in S_n}\#(\text{Fix}(\sigma))$$
Or, said differently
$$n!=\sum_{\sigma\in S_n}\#(\text{Fix}(\sigma))$$
A cool combinatorial fact within itself which is (at least to me) non-obvious (there is another proof using rep. theory though).
If you are interested in this sort of things a FANTASTIC book that will blow your minds is Algebraic Combinatorics Via Finite Group Actions by Bitten et. al It is freely available here.
Since we are painting the edges of squares, we assume that these four colorings are all considered the same, and should not be counted separately:
(It should be clear that painting triangular wedges is the same as painting edges, since there is a natural bijection between wedges and edges.)
It's not completely clear in the question, but we should probably also assume that the squares can be flipped over, so that these two colorings should also be considered the same:
That is the crucial question that decides whether to use $C_4$ or $D_4$: Are those two different colorings, or are they the same coloring? If they are the same coloring, then we say we are allowed to flip over the square, and flipping becomes part of the group we consider in applying the theorem. If they are different colorings, then reflections are not part of the group.
To apply the Cauchy-Frobenius-Burnside-Redfield-Pólya lemma, we begin by observing that our squares have the symmetry group $D_4$, which includes the four reflections. Then we count the number of colorings that are fixed points of a coloring under action by each element of $D_4$. Let $x$ be such an element, and suppose that $x$'s action on the square partitions the set of edges into $o(x)$ orbits. Then for a coloring to be fixed by $x$, all the edges in each orbit must be the same color. If there are $N$ different colors, then $N^{o(x)}$ are left fixed by the action of $x$.
The 8 elements of $D_4$ can be classified as follows:
- 2 orthogonal reflections, which divide the edges into 3 orbits ($2N^3$)
(For example, reflecting the square horizontally puts the left and right edges in one orbit, the top edge in a second orbit, and the bottom edge in a third orbit)
- 2 diagonal reflections, which divide the edges into 2 orbits ($2N^2$)
(For example, reflecting the square on the topleft-bottomright axis puts the top and left edges in one orbit, the bottom and right edges in the other)
- 2 quarter-turns, which put all the edges in a single orbit ($2N$)
- the half-turn, which divides the edges into 2 orbits ($N^2$)
- the identity, which leaves each edge in its own orbits ($N^4$)
The number of colorings with $N$ colors is the sum of the terms for each of these, divided by 8, the order of the symmetry group. Adding up the contributions from these we get $$\chi_{D_4}(N) = \frac18(N^4+2N^3+3N^2+2N).$$
This formula gives $\chi_{D_4}(0)=0, \chi_{D_4}(1)=1$ as we would hope. Hand enumeration of the $N=2$ case quickly gives 6 different colorings (four red edges; three red edges; two opposite red edges; two adjacent red edges; one red edge; no red edges) which agrees with the formula.
If reflections are not permitted, we delete the corresponding terms ($2N^3 + 2N^2$) from the enumeration, and divide by 4 instead of 8, as the symmetry group now has 4 elements instead of 8, obtaining instead $$\chi_{C_4}(N) = \frac14(N^4+N^2+2N).$$
This happens to have the same value as $\chi_{D_4}$ for $N<3$; this is because every coloring of the square with fewer than 3 colors has a reflection symmetry. The simplest coloring that has no reflection symmetry requires 3 colors: 
You asked “I am to include rotations?” The answer is probably yes, or the question would not have specified the edges of a square, which has a natural rotational symmetry. But suppose you wanted to consider to be different colorings. Then rotations of a coloring are not allowed, and the group you consider should be one that omits the rotation elements. In the extreme case, we can consider every coloring different, and then the group is the trivial group, and the same analysis says to omit all the terms except the $N^4$ contributed by the identity element, and we get $$\chi_{C_1}(N) = N^4$$ which is indeed the correct number of colorings.
Best Answer
The algorithm is correct. But note that you are coloring edges. What you did is not.
For example, for identity, there are actually $n^{12}$ elements fixed. Because there are $12$ edges and each edge has $n$ colors.