The key is to prove the following:
Theorem. Let $A$ and $B$ be matrices with real coefficients. If $A$ and $B$ are similar over $\mathbb{C}$, then they are similar over $\mathbb{R}$.
This problem appears, among other places, in Berkeley Problems in Mathematics, by de Souza and Nuno Silva (Problem 7.7.10 in the second edition; the problem has been used many times in the Prelim exam at Berkeley). The book offers two answers, though I think that one of the solutions (using the rational canonical form) is a bit sloppy.
Here is the other approach. Assume $A = UBU^{-1}$, with $U$ a complex matrix. Write $U=K+iL$, where $K$ and $L$ are real matrices, and assume that $L\neq 0$. Then $A(K+iL) = AU = UB = (K+iL)B$ and so the real parts and imaginary parts of these matrices are equal. That is, $AK = KB$ and $AL = LB$ (the problem is we don't know that $K$, by itself, is invertible).
Now, for any complex number $z$ we have $A(K+zL) = (K+zL)B$. Let $p(z) = \det(K+zL)$. Prove that $p$ is not identically zero, and take a real number that is not a root.
Once you have this theorem, your observation that $A$ and $B$ are similar over $\mathbb{C}$ implies the result you want.
(For what it is worth, the other argument given by the book is that the Rational canonical forms of $A$ and $B$ have to be the same, since they are the same over $\mathbb{C}$, and so $A$ and $B$ are similar over $\mathbb{R}$; the reason this is sloppy is that the rational canonical form is usually defined, for uniqueness purposes, in terms of the irreducible factors of the minimal/characteristic polynomials, and the rational blocks are companion matrices of powers of these irreducible factors. But the irreducible factors over $\mathbb{R}$ are not necessarily the same as the irreducible factors over $\mathbb{C}$, so that the "uniqueness" of the rational canonical form does not directly apply; an argument needs to be made that the equality over $\mathbb{C}$ implies an equality when the irreducible factors are taken over $\mathbb{R}$ instead, and this argument is missing in the book).