Here's a direct proof that if permutation matrices $A,B$ (of size $n\ge 0$) have the same characteristic polynomial (or equivalently are linearly equivalent, since these are diagonalizable) then they are conjugate as permutations, i.e., have the same cycle decomposition.
If $A,B$ have some cycle of common size, then we can "remove" it (which divides the characteristic polynomial by the same factor while reducing the matrix size). So we can suppose there are no cycles of common length in $A$ and $B$. In this case, we have to prove that $n=0$.
Consider a cycle of maximal length $m$ occurring in either $A$ or $B$, say in $A$. Then $\xi=\exp(2i\pi/m)$ is a root of the characteristic polynomial of $A$, and hence of $B$. But since $B$ has only cycles of length $<m$, its characteristic polynomial does not vanish at $\xi$, and we get a contradiction.