So first of all, I used the following from my lecture notes:
If $f \in \mathbb{Z}[x]$ is primitive (gcd of all the coefficients is 1) - $f$ irreducible in $\mathbb{Z}[x] \Leftrightarrow$ f irreducible in $\mathbb{Q}[x]$.
So now I only have to show that $f_n = x^n + x + 3$ is irreducible in $\mathbb{Z}[x]$ for all $n \geq 2. $
Is there a pattern I should be appealing to in some way?
If we had a decomposition in $\mathbb Z[x]$ $$x^n + x + 3=p(x)\cdot q(x)=(x^a+\dots+c_a)\cdot(x^b+\dots+d_b)$$ we would deduce $c_a\cdot d_b=3$ so that we would have, maybe after renaming the factors, $c_a=\pm 1$ (and of course $d_b=\pm 3$).
This means that for the (complex!) zeros $z_i$ of $p(x)$ we would have $\prod |z_i|=1$, so that at least one of those zeros, say $z_1$, must satisfy $|z_1|\leq 1$.
But then, since $z_1$ is also a zero of our original polynomial: $z_1^n+z_1+3=0$.
This is clearly impossible since $|z_1^n+z_1|\leq |z_1|^n+|z_1|\leq 2$.
This contradiction shows that $x^n + x + 3$ is actually irreducible.
Edit
I now realize that the same method proves that $x^n + x + p$ and $x^n + x - p$ are irreducible for any prime integer $p\geq 3$.