I would like some feedback as to whether this intuition is correct.
Conjugation in the symmetric group amounts to relabeling of the domain and codomain, preserving the cycle structure. For example,
Conjugating sigma by tau, $\tau\sigma\tau^{-1},$ preserves the original cycle structure (in colors) of the $(153)(24)$ permutation in $S_5,$ which essentially is $\Big(\tau(1)\tau(5)\tau(3)\Big)\Big(\tau(2)\tau(4)\Big)=(123)(45):$
or the result of composing $\tau(\sigma(\tau^{-1})):$
-i.e. a 3-cycle / 2-cycle permutation.
Since it is henceforth clear that conjugacy classes of $S_5$ will correspond to permutations that share the same cycle structure, and Cayley's theorem states that every group G is isomorphic to a subgroup of the symmetric group acting on G, what can we say that conjugacy preserves in a generic fashion for any type of (finite) group?
Best Answer
You are correct that conjugacy in $S_n$ is equivalent to sharing a cycle structure.
You are also correct that, via Cayley's theorem, this implies that conjugate elements in any group do have the same cycle structure for the translation action of $G$ on itself.
Aside: The (left-)translation action of $G$ on itself is the action that, for a given element $g$ of $G$, sends any element $h$ of $G$ to $gh$. The name "translation" is by analogy with the fact that when the Euclidean plane, seen as the vector space $\mathbb{R}^2$, acts on itself this way, each group element acts as a plane translation. In general, the translation action shares with plane translations the property that everybody moves, i.e. if $g\in G$ is not the identity, then $gh$ never equals $h$, so $g$'s action on $G$ causes every point to move somewhere else.
The identification in Cayley's theorem of a subgroup of $S_n$ isomorphic to $G$ is usually based on this action: one maps $g\in G$ to the permutation in $S_{|G|}$ describing the action of $g$ on $G$ by translation, and then proves that this map is a group isomorophism onto its image. End aside.
However, this fact is less interesting than you might think. In fact, if $g$ is an arbitrary element of an arbitrary finite group $G$, and $r$ is the order of $g$, then the cycle structure of $g$'s translation action on $G$ is always $|G|/r$ cycles of length $r$, regardless of anything else about $G$ or $g$. In particular, you cannot use the fact that two elements of $G$ have the same cycle structure for the translation action to detect conjugacy, because all it means is that they have the same order. (Certainly conjugate elements have the same order, but not conversely.)
The reason why $g$'s (left) translation action on $G$ always looks like $|G|/r$ cycles of length $r$ is because these cycles are nothing but the (right) cosets of the subgroup $\langle g\rangle$ of order $r$ generated by $g$. Indeed, given $h\in G$, $g$'s left translation action sends $h\mapsto gh \mapsto g^2h \mapsto \dots\mapsto g^{r-1}h\mapsto h$.
Addendum: More generally, suppose you have identified $G$ with some subgroup of $S_n$ (whether via the left translation action used in the proof of Cayley's theorem, or some other way).
The essential truth you seem to be asking after is that elements conjugate in $G$ will have the same cycle structure as elements of $S_n$. This is true exactly by your reasoning. If $\varphi:G\rightarrow S_n$ is an isomorphism of $G$ into a subgroup of $S_n$, and $g,g'$ are conjugate i.e. there exists $h\in G$ with $hgh^{-1} = g'$, then $\varphi(h)\varphi(g)\varphi(h)^{-1} = \varphi(g')$ since $\varphi$ is a group homomorphism, so $\varphi(g),\varphi(g')\in S_n$ are conjugate, and this means they have the same cycle structure by your argument.
But it is not true that you can use this to detect conjugacy; i.e. elements not conjugate in $G$ may still have the same cycle structure in $S_n$.
Here is an illustration:
In $A_4$, the elements $(123)$ and $(132)$ are not conjugate, even though they have the same cycle structure. The problem is that, although there are permutations that carry the labels of one to the labels of the other (e.g. $(23)$), they do not lie in $A_4$. These elements become conjugate in $S_4$, but in the smaller group they are not conjugate.