Two permutation matrices represent conjugate permutations iff they have same characteristic polynomial.

We'll first prove that the characteristic polynomial of a permutation matrix representing a permutation $\pi\in S_{n}$ having the cycle structure $1^{c_{1}}2^{c_{2}}...n^{c_{n}}$ is of the form $\prod_{j=1}^{n}(x^{j}-1)^{c_{j}}$.

The eigenvalues of any permutation matrix representing the cycle structure $1^{c_{1}}2^{c_{2}}...n^{c_{n}}$ are $i_{th}$ roots of unity counted with multiplicities $c_{i}$ (where i represents the cycle lengths), which is shown here. As we know that Eigenvalues are the roots of characteristic polynomial, the polynomial corresponding to these eigenvalues is clearly $\prod_{j=1}^{n}(x^{j}-1)^{c_{j}}$.

We'll prove that such representation is unique. Before that let's state a fact we'll use

The nth root of unity $\alpha = cos(\frac{2\pi}{n})+isin(\frac{2\pi}{n})$ does not satisfy $x^{k}-1 = 0$ for $0\lt k\lt n$. But for $k\gt n$ it satisfies $x^{k}-1 = 0$ for $k=nt$ where $t\in \Bbb N$.

Coming to the proof, Let $XP_{1}$ and $XP_{2}$ both have same roots of unity counted with multiplicities. But $XP_{1}$ and $XP_{2}$ differ in their representation i.e. They are like
$$XP_{1} = \prod_{j=1}^{n}(x^{j}-1)^{c_{j}}, XP_{2} = \prod_{j=1}^{n}(x^{j}-1)^{d_{j}}$$ Let $j_{1}$ be the greatest $j$ such that $c_{j}\neq d_{j}$. As per our assumption and the fact we stated above, the occurence of the $j_{1}$ root of unity $\alpha = cos(\frac{2\pi}{j_{1}})+isin(\frac{2\pi}{j_{1}})$ in $XP_{1}$ and $XP_{2}$
$1$. Due to $(x^{j}-1)^{c_{j}}$ for $j\gt j_{1}$ is same in both.
$2$. Due to $(x^{j}-1)^{c_{j}}$ for $j\lt j_{1}$ is zero.
$3$. Due to $(x^{j}-1)^{c_{j}}$ for $j=j_{1}$ viz $c_{j_{1}}$,$d_{j_{1}}$ is different.

But it means multiplicities of $\alpha$ are different in $XP_{1}$ and $XP_{2}$. We reach a contradiction. Hence $c_{j} = d_{j} \space \forall j\in \Bbb N$

Now if two permutation matrices have the same characteristic polynomial they must have the same cycle type and hence they must represent conjugate permutations in $S_{n}$.

If a matrix $A$ has eigenvalues $\lambda_1,\dots,\lambda_n$ (listed with algebraic multiplicity), then $A^k$ has eigenvalues $\lambda_1^k,\dots,\lambda_n^k$, and so $\operatorname{tr}(A^k)=\sum_i\lambda_i^k.$ By Newton's identities, $\sum_i\lambda_i^k$ can be expressed in terms of the elementary symmetric polynomials in the $\lambda_i$, which are just (up to sign) the coefficients of the characteristic polynomial of $A$.

The upshot is that if $A$ and $B$ have the same characteristic polynomial, then $\operatorname{tr}(A^k)=\operatorname{tr}(B^k)$ for all $k$. Now if $A$ is a permutation matrix corresponding to a permutation $\pi$, then $\operatorname{tr}(A^k)$ is just the number of fixed points of $\pi^k$. So, it suffices to show that if $\pi,\rho\in S_n$ are such that $\pi^k$ and $\rho^k$ have the same number of fixed points for each $k$, then $\pi$ and $\rho$ have the same cycle structure. To show this, let $a_k$ be the number of $k$-cycles in $\pi$ and let $b_k$ be the number of $k$-cycles in $\rho$. Note then that the number of fixed points of $\pi^k$ is $\sum_{d\mid k}da_d$ and the number of fixed points of $\rho^k$ is $\sum_{d\mid k}db_d$. We know these are equal, and using strong induction on $k$ we may assume that $a_d=b_d$ for every proper divisor $d$ of $k$. It follows that $ka_k=kb_k$ and thus $a_k=b_k$.