Given two elements $g,h$ in a finite group $G$ of the same order, does there exist a finite group $G'$ containing $G$ where they are conjugate?

This is a theorem of Bernhard Neumann and his wife (and, as he once told me, can be found in his Collection of Works; he even told me which volume I should look at, but I do not remember; I am sure mathsci can help). A "modern" proof of that fact is easy. Basically suppose that two finite groups $G$ and $H$ are isomorphic. Then take $F=G\times H$ and the HNN extension $T$ of $F$ with associated subgroups $G, H$. In $T$, the subgroups $G$ and $H$ are conjugate. Now, $T$ is infinite, but as every HNN extension of a finite group, $T$ is residually finite because it is virtually free (say, by Stallings ends theorem). Hence $T$ has a finite quotient $R$ such that the natural maps from $G$ and $H$ into $R$ are embeddings. Thus $G$ and $H$ are conjugated subgroups of a finite group $R$.

Edit 1: The paper is this: MR0064042 Neumann, B. H.; Neumann, Hanna "Partial endomorphisms of finite groups." J. London Math. Soc. 29, (1954). 434–440.

If $G$ and $H$ are given as subgroups in the same finite group $F$, then there is no need to take $F= G\times H$.

Edit 2: In fact the paper by Neumanns cited above proves a much stronger result when there is only a homomorphism from $G$ to $H$ (the question is then whether it extends to an endomorphism of a bigger finite group). The fact about arbitrary isomorphic finite subgroups is proved first in Neumann, B. H. (notice the absence of Hanna Neumann) An essay on free products of groups with amalgamations. Philos. Trans. Roy. Soc. London. Ser. A. 246, (1954). 503–554. The paper gives two proofs of this fact (Corollary 18.3). The first uses amalgamated products and is essentially the proof above. The second proof is attributed to Ph. Hall and is essentially the same as Will Sawin's proof discussed in the comments.

Two subgroups are isomorphic iff they are conjugate in some larger finite group.

If you have two subgroups $A,B$ of a finite group $G$ and $\sigma: A\to B$ is an isomorphism. Then there exists a group $G'$ containing $G$ and an element $g'\in G'$ such that $\sigma$ is induced by conjugation by $g'$. For your question this follows by taking $A,B$ to be the cyclic groups generated by your two elements of the same order.

Since the question was reopened in spite of a duplicate in MathSE, I also "duplicate" my answer from there (a little improved anyway), so as to provide a self-contained answer. I leave it cw since it relies on ideas form other answers and comments.

(a) The answer to the OP's question is yes, and more generally one has:

Fact. Consider a finite group $F$ and two subgroups $A,B$ with an isomorphism $t:A\to B$. Then one can embed $F$ in a larger finite group in which $A$ and $B$ are conjugate (the conjugation inducing the isomorphism $t$ from $A$ to $B$).

This applies in particular to the case when $A,B$ are cyclic subgroups of the same order.

Proof of the fact. $A$ has two free actions on $F$, one being given by $a\cdot g=ag$, the other by $a\cdot g=t(a)g$. Writing $k=|F/A|$, find $k$ points $x_1,\dots,x_k$, one in each orbit of the first action, and $k$ points $y_1,\dots,y_k$, one in each orbit of the second action. Then extend the assignment $x_i\mapsto y_i$ to a permutation $\sigma$ of $F$, by the assignment $\sigma(ax_i)=t(a)y_i$. This is well-defined by freeness of the action. Then $$\sigma(abx_i)=t(ab)y_i=t(a)t(b)y_i=t(a)\sigma(bx_i)$$ for all $a,b\in A$ and $i$, and thus $\sigma(ag)=t(a)\sigma(g)$ for all $a\in A$ and $g\in F$. In other words, $\sigma\circ L_a=L_{t(a)}\circ \sigma$. So in the permutation group of $F$, where $F$ is identified to its image through left multiplication, the isomorphism $t:A\to B$ is realized by conjugation by $\sigma$. $\Box$

This is essentially Will's argument, which was only written for $A,B$ cyclic.

(b) In the same setting, the universal group in which $A$ and $B$ are conjugate through $t$, is the HNN extension $H$ of $(F,A,B,t)$, defined by the relative presentation $$\langle u,G\mid uau^{-1}=t(a),\forall a\in A\rangle.$$

It is well-known that this HNN-extension is virtually free and hence residually finite. Thus, there exists a finite quotient of $H$ in which $F$ is mapped injectively, and in this quotient $A$ and $B$ are indeed conjugate (by $t$).

Of course this argument (mentioned by HJRW in the comments to Will's answer), which looks somewhat immediate at first glance, is less elementary than the one in (a) since it relies on residual finiteness of HNN extensions of finite groups; anyway it's a very natural proof since the construction is universal.