It looks like it can be solved quickly using a branch-and-bound procedure, assuming that the number of elements in the permutation is not excessively large.
(Notation: I'll use capital letters to specify permutations, and lower case letters to specify individual elements of the permutation); in addition, I'll take the convention that $XY$ means "apply the permutation $X$ to the elements, and then apply the permutation $Y$)
The algorithm is straight-forward; we know that $XY = ZX$, so:
- We pick an arbitrary element of the permutation $a$ and assume that $X(a) = b$ (where $b$ is a previously output of $X$). We then can deduce the value $XY(a) = d$ (where $d = Y(b)$). In addition, we have $Z(a) = c$ (for some element $c$), and so we can then deduce $X(c) = d$.
Assuming that $c, d$ are previously unknown inputs/outputs of $X$, we reiterate the same logic, which will give us another pair $X(e) = f$.
We keep on doing this until it gives us a pair that we've seen before, or it gives an inconsistent pair (that is, it assigned the same $X(g)$ value to two different outputs, or it gives us a set $g \ne h, i$ with $X(g) = X(h) = i$
If it gives us an inconsistent pair, we drop back to the previous assumption that $X(a) = b$, and modify $b$, and restart our computation from there.
If it gives us a pair that we've seen before, and there are still unassigned inputs/outputs to $X$, we restart at the beginning, arbitrarily selecting a previously unassigned input/output pair.
This won't give a unique value of $X$; that's because there are multiple solutions, and this will pick one arbitrarily.
Update: I just wrote a quick (and fairly suboptimal) C program to do this; it could find a conjugate (where one existed) given two permutations over 10,000 elements in under a second...