So I've said $x^{2}+1$ is reducible over $\mathbb{F}_{p^{n}} \iff \mathbb{F}_{p^{n}}$ contains a root $\alpha$. Hence if $\alpha$ is such a root then $\alpha^2 = -1$ so that $\alpha^4 =1$ and hence $|\alpha|=4$ in $\mathbb{F}^{\times}_{p^{n}}$ and hence $4\mid p^n -1 \implies p^n \equiv 1\bmod 4$. Hence if $p^{n}$ is congruent to $0,2,3$ mod $4$ then $x^{2}+1$ is irreducible over $\mathbb{F}_{p^{n}}$.
My problem is with $p^{n}$ congruent to $1$ mod $4$ being sufficient to conclude that $x^{2}+1$ is reducible. How can I show this?
Hint: The multiplicative group $\mathbb{F}_{p^n}^\times$ is a cyclic group. Recall that a cyclic group of size $m$ has the property that there exists an element of order $d$ for every divisor $d\mid m$.
Also, you're not quite correct on the condition; sometimes a root of $x^2+1$ in $\mathbb{F}_{p^n}$ will not have order $4$ in the multiplicative group. Can you figure out when?