What is the decomposition of the ring $\mathbb{F}_p[x]/(x^n-1)$?

I think that your approach via the cyclotomic polynomials $\Phi_d (X)$ is misleading, because their irreducibility is a "global" property (all primes intervene), whereas your question here is a "local" one (a fixed prime $p$ is given). Let us start afresh and write $n=p^r m$, $p$ not dividing $m$. Then, as in the answer of @Jyrki Lahtonen, $X^n - 1 = (X^m - 1)^{p^r}$ in $\mathbf F_p [X]$ , so that we need only to study the decomposition of $X^m - 1$ . By Galois theory, this amounts to study the extension $\mathbf E =\mathbf F_p(\zeta_m)$ over $\mathbf F_p$, where $\zeta_m$ is a primitive $m$-th root of unity. If $f$ is the degree of $\mathbf E/\mathbf F_p$, by the theory of finite fields, $G =Gal(\mathbf E/\mathbf F_p)$ is cyclic of order $f$, generated by the Frobenius automorphism $\sigma_p$ defined by $\sigma_p(x) = x^p$. It follows that $f$ is the order of $p$ mod $m$ (cp. your remark on the irreducible factors of $\Phi_d (X)$ mod $p$) and $G$ can be identifed with a cyclic subgroup of order $f$ of $(\mathbf Z /m\mathbf Z)^*$. It remains to deduce from this the decomposition of $X^m - 1$ in $\mathbf F_p [X]$.

For any $d$ dividing $m$, let $\zeta_d$ be any primitive $d$-th root of unity. Since $G$ permutes transitively the primitive roots $\zeta_d$ (which are all distinct because $p$ does not divide $m$), the polynomial $\Psi_d (X) :=$ product of the $(X - \zeta_d)$ 's belongs to $\mathbf F_p [X]$, and $X^m - 1$ is the product over all $d$ dividing $m$ of the $\Psi_d (X)$'s. Moreover $\Psi_d (X)$ is irreducible : suppose that it decomposes as a product $g_1. ... g_s$ of distinct irreducible polynomials in $\mathbf F_p [X]$ (no power because all the zeroes are simple); if $\zeta$ is a root of $g_1$ (so that $g_1$ is the minimal polynomial of $\zeta$ over $\mathbf F_p$), then $\zeta ^p$ will be a root of some $g_j$, but since $g_j (\zeta ^p)=(g_j(\zeta))^p=0$, $g_1$ will divide $g_j$, so $g_1 = g_j$ up to a multiplicative constant, a contradiction.

In conclusion, the decomposition of $X^m - 1$ in $\mathbf F_p [X]$ is the product of all the $\Psi_d (X)$'s for $d$ dividing $m$. This is the analog (but not the reduction) mod $p$ of the decomposition of $X^m - 1$ into the product of the cyclotomic polynomials $\Phi_d (X)$.