Original post by SsEeThere's a "method" for this. You perhaps know that two elements are conjugate if and only if they have the same cycle structure. So you can write them something like:
g = (a_1, a_2, ..., a_k1)(b_1, b_2, ..., b_k2)...(z_1, z_2, ..., z_kn)
and
h = (A_1, A_2, ..., A_k1)(B_1, B_2, ..., B_k2)...(Z_1, Z_2, ..., Z_kn)
The conjugating permutation x (so that x^(-1)gx = h) is the one taking a_1 to A_1, a_2 to A_2, ..., z_kn to Z_kn (assuming you compose permutations left to right).
So for example, in S6 take g = (12)(34)(5)(6) and h = (23)(16)(4)(5). They have the same cycle structure. Let x be the permutation taking 1->2, 2->3, 3->1, 4->6, 5->4 and 6->5. So x = (123)(465). You can work out that x^(-1) is (132)(456). Then
x^(-1)gx = (132)(456)(12)(34)(5)(6)(123)(465) = (16)(23)(4)(5) = h
Note, there are options here. I could have written h as (23)(16)(5)(4). Then x would be (123)(46)(5) which also works. So to find x you just line up the cycles eg. by putting them in order of length (including cycles of length 1) and read off what x does to each number.