If $\alpha$ is a root of $f(x)=x^p-x-b$ in the algebraic closure of $\mathbb{F}_{p}$, then it can be seen (by using the Frobenius automorphism $x \to x^p$) that the rest of the roots of $f$ are given by $\alpha +i, 1 \le i < p$.
If $f(x)$ factors as $\prod_{j=1}^{r} g_j(x)$ over $\mathbb{F}_{p^n}$, it means that each $g_j$ is the minimal polynomial of some $\alpha + i$. Those minimal polynomials must be of the same degree, since if $h(x)$ is irreducible and vanishes on $\alpha+i$ then $h(x-i+j)$ is also irreducible and vanishes on $\alpha+j$.
Let $d=\deg g_1$. Then by comparing degrees, $p = rd$. There are 2 cases -
$d=1$ - in this case, $f$ splits into linear factors, so it must have a root in $\mathbb{F}_{p^n}$. But if $\alpha^{p}-\alpha-b=0$ then $\alpha^{p^n} = \alpha + nb$ By induction (apply the Frobenius automorphism $x \to x^p$ on both sides). $y \in \mathbb{F}_{p^n}$ iff $y^{p^n} = y$, so we must have $nb=0$, i.e. $p|n$.
$d=p$ - in this case, $f$ is irreducible.
In conclusion, in $\mathbb{F}_{p^p}$ $f$ splits into linear factors (and also in any finite field containing it). In the rest of cases ($p \nmid n$), $f$ is irreducible. $\blacksquare$
Fun related fact: $x^{p^n}-x$ is the product of all irreducible polynomials of degree dividing $n$.