The cycle structure of a permutation $\sigma \in S_n$ pops up naturally if we consider the action of $\langle \sigma \rangle$ as a group of permutations on the set $I_n:=\{1,\dots,n\}$ ("natural action"). By the Orbit-Stabilizer Theroem (O.S.T.), we get:
$$|O_\sigma(j)||\operatorname{Stab}_\sigma(j)|=o(\sigma), \forall j\in I_n \tag 1$$
where:
$$\operatorname{Stab}_\sigma(j):=\{\sigma^k\mid \sigma^k(j)=j\} \le \langle\sigma\rangle, \forall j\in I_n \tag 2$$
Now, given $\alpha \in S_n$, it is $(\alpha\sigma\alpha^{-1})^k=\alpha\sigma^k\alpha^{-1}$ (induction on $k$), so we get:
\begin{alignat}{1} \operatorname{Stab}_{\alpha\sigma\alpha^{-1}}(j)&=\{\alpha\sigma^k\alpha^{-1}\mid (\alpha\sigma^k\alpha^{-1})(j)=j\} \\ &=\{\alpha\sigma^k\alpha^{-1}\mid \alpha(\sigma^k(\alpha^{-1}(j)))=j\} \\ &=\{\alpha\sigma^k\alpha^{-1}\mid \sigma^k(\alpha^{-1}(j))=\alpha^{-1}(j)\} \\ &=\{\alpha\sigma^k\alpha^{-1}\mid \sigma^k \in \operatorname{Stab}_\sigma(\alpha^{-1}(j))\} \\ &=\alpha \operatorname{Stab}_\sigma(\alpha^{-1}(j)) \alpha^{-1}, \forall \alpha \in S_n,\forall j\in I_n\\ \tag 3 \end{alignat}
whence:
$$|\operatorname{Stab}_{\alpha\sigma\alpha^{-1}}(j)|=|\operatorname{Stab}_\sigma(\alpha^{-1}(j))|, \forall \alpha \in S_n,\forall j\in I_n \tag 4$$
But since $\forall \alpha \in S_n, o(\alpha\sigma\alpha^{-1})=o(\sigma)$, $(4)$ implies (again by the O.S.T.):
$$|O_\sigma(\alpha^{-1}(j))|=|O_{\alpha\sigma\alpha^{-1}}(j)|, \forall \alpha \in S_n, \forall j\in I_n \tag 5$$
Therefore, for every $\alpha \in S_n$, the orbits induced by $\langle \alpha\sigma\alpha^{-1}\rangle$ and $\langle \sigma\rangle$ are pairwise of equal size. Moreover, if we denote by $\mathcal{O}$ the set of orbits, we have:
\begin{alignat}{1} |\mathcal{O}_{\alpha\sigma\alpha^{-1}}| &= \frac{1}{o(\alpha\sigma\alpha^{-1})}\sum_{j=1}^{n}|\operatorname{Stab}_{\alpha\sigma\alpha^{-1}}(j)| \\ &=\frac{1}{o(\sigma)}\sum_{j=1}^{n}|\operatorname{Stab}_\sigma(\alpha^{-1}(j))| \\ &=\frac{1}{o(\sigma)}\sum_{i=1}^{n}|\operatorname{Stab}_\sigma(i)| \\ &=|\mathcal{O}_\sigma| \\ \tag 6 \end{alignat}
So, for every $\alpha \in S_n$, the natural actions of $\langle\sigma\rangle$ and $\langle\alpha\sigma\alpha^{-1}\rangle$ induce the same number of orbits of the same size in pairs, namely $\sigma$ and $\alpha\sigma\alpha^{-1}$ have the same cycle structure.
I would like to prove within this framework the converse implication (if two permutations have the same cycle structure, then they are conjugate), but I'm finding it harder. Could you give me some hint, please?
Hint:
1) It is enough to show that two cycles of the same length are conjugate.
2) Use the formula: $\enspace\sigma\, (a_{i_1}\,\dots\,a_{i_k})\,\sigma^{-1}=(a_{\sigma (i_1)}\,\dots\,a_{\sigma (i_k)})$.