Here's a possible method:

We might as well assume that $A$ is already a permutation matrix -- just conjugate $A$ and $B$ by the same unitary matrix $C$ and relabel.

Now if we are looking to conjugate $B$ to a permutation matrix AND retain $A$ as a permutation matrix, then we'll need to conjugate by something that centralizes $A$ -- so our conjugating matrix, call it $X$, must lie in $C_G(A)$, where $G=U(n)$.

(Note: you might wonder about the possibility that $A$ could be conjugated to a **different** permutation matrix instead, therefore allowing a larger choice for $X$; however this question assures us that if we were to do this, we could then conjugate by a permutation matrix to return $A$ to its original form, without affecting whether or not $B$ is a permutation matrix.)

$C_G(A)$ is easy enough to calculate -- especially if $A$ is made up of cycles of different lengths. Now let $\mathcal{B}$ be the natural basis. We use the reformulation of @YCor to consider what happens when we apply $X$ to $\mathcal{B}$. So, for instance, if
$$A=\begin{pmatrix} & 1 & \\ & & 1 \\ 1 & & \end{pmatrix}$$
then the elements of $C_G(A)$ are unitary matrices of the form
$$
X=\begin{pmatrix} a & b & c \\ c & a & b \\ b & c & a \end{pmatrix}.$$
If we apply the matrix $X$ to the natural basis, then we obtain a basis of the form
$$\left\{\begin{pmatrix}a \\ c \\ b \end{pmatrix}, \begin{pmatrix} b \\ a \\ c\end{pmatrix}, \begin{pmatrix} c \\ b \\ a \end{pmatrix}\right\}$$
where $a,b,c$ are restricted to ensure the basis is orthonormal.

These are all of the orthonormal bases for which $A$ is the permutation matrix written above. Now $B$ will be a permutation matrix with respect to one of these bases, say $\mathcal{B}_1$, if and only if, for all $v\in \mathcal{B}_1$, $Bv\in\mathcal{B}_1$. One simply has to test whether any of the listed bases have this property.

Remarks:

- I'd like to find a nice, neat way to do that last bit -- check whether the matrix $B$ fixes any of the bases thrown up by considering the centralizer of $A$... But it's not obvious to me that one can do this in any efficient sort of a way...
- The centralizer of $A$ will be a lot larger if there are cycles of the same length -- and this will yield a lot more possible bases to test at the end. One should clearly label $A$ and $B$ so that $A$ has as few cycles as possible.

So, algorithmically, it might be most efficient to use the observations in the comments about products of $A$ and $B$: take a few products of $A$ and $B$ of some bounded length -- if any of these can't be conjugated to permutation matrices, then, obviously, you stop. If they ALL can be conjugated to a permutation matrix, then choose whichever product resulted in a permutation matrix with fewest repeated cycles.

**Added later**: In fact, we can make that final step (where we study the action of the matrix $B$ on a bunch of bases) much more efficient if we check the isomorphism type of the group $\langle A, B\rangle$; this must be isomorphic to a subgroup of $S_n$, in which $A$ must correspond to the given permutation matrix (so, for instance, if $A$ was the matrix in the example above, then its image in $S_n$ would be the 3-cycle $(1,2,3)$). This allows us to explicitly list the possible permutations corresponding to $B$. For each of these possibilities, one has an explicit action on the basis $\mathcal{B}_1$.

So, for instance, in the example above, if $B$ were to correspond to the element $(1,2)$, then its action on the basis $\mathcal{B}_1$ would need to swap the first two basis elements. Checking this specific property is much more straightforward than checking if $B$ preserves any of the possible bases obtained using the centralizer of $A$.

2more comments