We know that
If a polynomial $p$ is reducible over $\mathbb{Z}$, then it is reducible over $\mathbb{Z}_n$,
but
reducibility over $\mathbb{Z}_n$ doesn't always imply reducibility over $\mathbb{Z}$.
My question is, are there certain conditions on $p$ where this actually would work?
In fact it is possible for an irreducible polynomial to be reducible $\bmod n$ for all $n$. Let me indicate how this works for prime moduli for simplicity. The two key results are the following. Suppose $f(x) \in \mathbb{Z}[x]$ is a monic irreducible polynomial of degree $d$ with Galois group $G$. If $p$ is a prime not dividing the discriminant $\Delta$ of $f$, then there is a factorization
$$f(x) \equiv \prod f_i(x) \bmod p.$$
where the $f_i(x)$ are distinct irreducible polynomials of degree $d_i$.
Key result #1: $(d_1, d_2, \dots)$ is the cycle decomposition of an element of $G$ acting on the roots of $f$.
Key result #2: A cycle decomposition $(d_1, d_2, \dots)$ occurs in the above factorization $\bmod p$ with the same probability that it occurs in $G$.
Key result #2 follows from a special case of the Chebotarev density theorem called the Frobenius density theorem; it is less well-known but, I am told, substantially easier to prove.
Corollary: $f(x)$ is reducible $\bmod p$ for all primes $p$ iff $G$ does not contain a $d$-cycle.
If $d$ is prime, then $G$ must always contain a $d$-cycle (exercise).
Corollary: If $d = \deg f$ is prime and $f(x)$ is reducible $\bmod p$ for all primes $p \nmid \Delta$, then $f(x)$ is reducible.
The first composite case is $d = 4$. In this case it's possible for $G$ to be the Klein four group $C_2 \times C_2$, which does not contain a $4$-cycle. Explicit examples were written down by Hilbert and aren't hard to write down in any case, but I can't remember one off the top of my head.
