Theorem: Let $\alpha$ be an algebraic integer such that $\mathbb{Z}[\alpha]$ is integrally closed, and let its minimal polynomial be $f(x)$. Let $p$ be a prime, and let
$\displaystyle f(x) \equiv \prod_{i=1}^{k} f_i(x)^{e_i} \bmod p$
in $\mathbb{F}_p[x]$. Then the prime ideals lying above $p$ in $\mathbb{Z}[\alpha]$ are precisely the maximal ideals $(p, f_i(\alpha))$, and the product of these ideals (with the multipicities $e_i$) is $(p)$. (Theorem 8.1.3.)
In this particular case we have $f(x) = \Phi_n(x)$. When $(p, n) = 1$, its factorization in $\mathbb{F}_p[x]$ is determined by the action of the Frobenius map on the elements of order $n$ in the multiplicative group of $\overline{ \mathbb{F}_p }$, which is in turn determined by the minimal $f$ such that $p^f - 1 \equiv 0 \bmod n$ as described in Chandan's answer. (This $f$ is the size of every orbit, hence the degree of every irreducible factor.) When $p | n$ write $n = p^k m$ where $(m, p) = 1$, hence $x^n - 1 \equiv (x^m - 1)^{p^k} \bmod p$. Then I believe that $\Phi_n(x) \equiv \Phi_m(x)^{p^k - p^{k-1}} \bmod p$ and you can repeat the above, but you'd have to check with a real number theorist on that. (Edit: Indeed, it's true over $\mathbb{Z}$ that $\Phi_n(x) = \frac{ \Phi_m(x^{p^k}) }{ \Phi_m(x^{p^{k-1}}) }$.)
