My background on number theory is very weak, so please bear with me...
Given two matrices $A$ and $B$ in $\mathbb{Z}^{n\times n}$. Assume that for every prime $p$, the images of $A$ and $B$ in $\mathbb{F}_p^{n\times n}$ are similar to each other. Does this yield the existence of a matrix $X\in\mathrm{SL}_n\left(\mathbb{Z}\right)$ satisfying $AX=XB$ ? What if we additionally assume $A$ and $B$ to be similar in $\mathbb{Q}^{n\times n}$ ?
Your question reminds me of a classical theorem of Latimer and MacDuffee (Annals of Math. 1933). To be sure, the theorem does not answer your question, but it seems relevant.
A nice contemporary treatment of this theorem (with references) can be found at
http://www.math.uconn.edu/~kconrad/blurbs/gradnumthy/matrixconj.pdf
[At the moment that I write this, math.uconn.edu seems to be down. I presume this is only temporary!]
The answer is no. Here is a counter-example $$\left( \begin{matrix} 0 & -5 \\\\ 1 & 0 \end{matrix} \right) \quad \mbox{and} \quad \left( \begin{matrix} -1 & -3 \\\\ 2 & 1 \end{matrix} \right).$$
Both of these matrices have characteristic polynomial $x^2+5$. For $p \neq 2$, $5$, this polynomial has no repeated factors so any matrices with this polynomial are similar. By the same argument, they are similar over $\mathbb{Q}$. By brute force computation, they are also similar at $2$ and $5$.
However, they are not similar over $\mathbb{Z}$. Consider $\mathbb{Z}^2$ as a module for $\mathbb{Z}[t]$ where $t$ acts by one of the two matrices above. Both of these matrices square to $-5$, so these are in fact $\mathbb{Z}[\sqrt{-5}]$-modules. If the matrices were similar, the similarity would give an isomorphism of $\mathbb{Z}[\sqrt{-5}]$-modules. But these are not isomorphic: the former is free on one generator while the latter is isomorphic to the ideal $\langle 2, 1+ \sqrt{-5} \rangle$.
In general, the way to classify similarity of matrices over $\mathbb{Z}$ is the following: If the matrices do not have the same characteristic polynomial over $\mathbb{Q}$, they are not similar. If they do, let $f$ be the characteristic polynomial and let $R=\mathbb{Z}[t]/f(t)$. Then your matrices give $R$-modules, and the matrices are similar if and only if the $R$-modules are isomorphic. If $R$ is the ring of integers of a number field, then $R$-modules are classified by the ideal class group. In general, they are related to the ideal class group, but there are various correction factors related to how $R$ fails to be the ring of integers of its fraction field (or how it fails to be a domain at all). I don't know the details here.
It is a well known fact that over any field a square matrix and its transpose are conjugated. You should look for a matrix $A$ over the integers such that $A$ and $A^t$ are non conjugated. If I did not messed up my calculations the matrix with entries $A_{1,1}=1, A_{1,2}=2, A_{1,3}=3, A_{1,4}=4$ has the property that $A$ and $A^t$ are non-conjugated by any element of $GL_2(\mathbb{Z})$. On the other hand they are conjugated over any field(you can always think of them as elements in $M_{2 \times 2}(F)$ for any field $F$).
