What is an intuition behind conjugate permutations?

Conjugation of a permutation is the same as renaming the objects on which your group of permutations acts. Therefore, two permutations are conjugate iff they act in the "same way", just on different elements. For instance, in $S_5$, the permutations $(123)(45)$ and $(145)(23)$ are conjugate, since they essentially do the same thing.

A little more explicitly:

Let's say you have the permutation $\alpha$ with $\alpha(1) = 3$, $\alpha(2) = 1$, $\alpha(3) = 2$. Let's say your are afraid of numbers, so to make this permutation friendly you use letters instead. You relabel $1$ as $a$, $2$ as $b$, $3$ as $c$ to get a new permutation $\beta$ of the letters $\{a,b,c\}$. We get $\beta(a) = c$, $\beta(b) = a$, $\beta(c) = b$.

To figure out more carefully what is going on, define $p:\{a,b,c\} \rightarrow \{1,2,3\}$ by $p(a) = 1,p(b) = 2, p(c) = 3$, so that $p$ is the "translator" between your sets of symbols. You want to know where $\alpha$ should do in this translated alphabet. To find out what should happen to $a$, first translate: $p(a) = 1$. Then apply $\alpha$: $\alpha(1) = 3$. Finally, translate back using $p^{-1}$: $p^{-1}(3) = c$. So the "translated" version of $\alpha$ is the map $\beta = p^{-1} \alpha p$ with $\beta(a) = c$. W get $$\beta(a) = p^{-1}\alpha p(a) = p^{-1} \alpha(1) = p^{-1}(3) = c,$$ $$\beta(b) = p^{-1} \alpha p(b) = p^{-1} \alpha(2) = p^{-1} (1) = a,$$ $$\beta(c) = p^{-1} \alpha p(c) = p^{-1} \alpha (3) = p^{-1} (2) = b$$ which is what we want.

Here we're using two sets of symbols, $\{1,2,3\}$ and $\{a,b,c\}$, but we might as well relabel using the same set of symbols $\{1,2,3\}$ and $\{1,2,3\}$. The same idea works, and then you have the notion of conjugacy in $S_n$: if $\beta = p^{-1} \alpha p$, then $\beta$ is just given by taking $\alpha$ and relabeling the symbols using $p$ as a "translation".