Suppose $ P(x) = x^tQ(x)$, with $ Q(0) \not = 0$. Then $ (m, n) = 1 \Rightarrow (Q(m), Q(n)) = 1$. Taking a large prime $ m$, we see that either $ Q$ is constant or there is a prime $ p$ such that $ p|Q(m)$. If $ p = m$ then $ m|Q(m) \Rightarrow m|Q(0)$, witch is avoided for $ m$ large enough. Then $ p \not = m$. So $ (m, m + p) = 1$ but $ Q(m + p) \equiv Q(m) \equiv 0 \text{ } mod \text{ } p$, contradiction. Thus, $ Q$ is constant and $ P = \pm x^t, \text{ } t \ge 0$.

Notice that for all $n\in\mathbb{Z}$, if there exists a prime dividing $P(n)$ that doesn't divide $n$, we look at $(n+p,n) = 1\implies (P(n+p),P(n)) = 1$. This is absurd. Hence all the primes dividing $P(n)$ also divides $n$. Now if say $P$ is not constant, then by schur's there exists infinitely primes dividing $P(n)$ for some $n$, hence by the above observation we see that there then exists infinitely many primes dividing $P(0)$, implying that $P(0) =0$. We may proceed this argument on $Q(x) = P(x)/x$ and so on, hence we obtain $P(x) = \pm x^t$ for nonnegative integers $t$.

A small thought: what would the answer be if the condition is $(P(m),P(n))=1\Rightarrow (m,n)=1$?

Consider a prime $p$ such that $p \nmid n$. Then, take $m = n + p$ and we have $\gcd(P(n + p), P(n)) = 1 \implies \gcd(P(n + p) - P(n), P(n)) = 1$. We have $p = (n + p) - p \mid P(n + p) - P(n) \implies p \nmid P(n)$. So, $p \nmid x \implies p \nmid P(x)$. So, $P(x) \mid x^k$ for large enough $k$. If $P$ is constant, $P \equiv \pm1$, so assume $P$ is non-constant. Let $P(x) = a_nx^n + a_{n - 1}x^{n - 1} + \dots + a_1x + a_0$. If $a_0 \neq 0$, then there will exist $x$ such that $\gcd(x, a_0) = 1$ and a prime $p$ such that $p \mid P(x)$ and $p \nmid x$, a contradiction. So, $P(x) = a_nx^n + a_{n - 1}x^{n - 1} + \dots + a_1x = x(a_nx^{n - 1} + \dots a_1)$. If $a_1 \neq 0$, there will exist large $x$ such that $\gcd(x, a_1) = 1$ and henceforth a prime $p$ such that $p \mid P(x)$ and $p \nmid x$, a contradiction. Continuing, we have $a_0 = a_1 = \dots = a_{n - 1} = 0$. So, $P(x) = a_nx^n$ and clearly $a_n \pm 1$. Hence, our answer is $P(x) = \pm x^k$.