The answer is yes by an old theorem of Brauer. In fact, permutation matrices are conjugate over any field if and only if they are conjugate by permutation matrices. See this beautiful proof by Kovacs https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/blms/14.2.127.

The answer is yes by an old theorem of Brauer. In fact, permutation matrices are conjugate over any field if and only if they are conjugate by permutation matrices. See this beautiful proof by Kovacs https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/blms/14.2.127.

Edit. Let me add that this was originally proved in the paper Brauer, Richard, On the connection between the ordinary and the modular characters of groups of finite order. Ann. of Math. (2) 42 (1941), 926–935. Laci Kovacs gave a very short elegant proof that works in all characteristics in the link. I believe the easiest characteristic $0$ proof is the one I sketched in the comments to @Ycor's answer, namely that if $A$ and $B$ are conjugate matrices, then $A^m$ and $B^m$ have the same trace for all $m>0$. This means that the corresponding permutation matrices have the same number of elements with an orbit of size dividing $m$ for all $m$. An easy inductive argument (or Mobius inversion argument on the divisor poset) then shows they have the the same number of orbits of each size and hence are conjugate in the symmetric group.