I understand that the Steenrod algebra for finite fields with $p$ elements ($p$ prime) is understood, but do we know what the Steenrod algebra is for all finite fields?
Namely, what is $H\mathbb F_{p^n}^* \left ( H \mathbb{F}_{p^n} \right )$ for $p$ prime?
I'm afraid you don't get any new topological classes. Write $q = p^n$ and $\mathcal{A}^*$ for the mod $p$ Steenrod algebra; we also suppress the $H$ in the notation for Eilenberg-MacLane spectra.
We have $$\DeclareMathOperator{\Map}{Map} \Map(\mathbb{F}_q, \mathbb{F}_q) \simeq \Map_{\mathbb{F}_p}(\mathbb{F}_q, \Map(\mathbb{F}_p, \mathbb{F}_p) \otimes_{\mathbb{F}_p} \mathbb{F}_q).$$ The "mod $q$ Steenrod algebra" is the homotopy groups of this mapping object, which we can compute using the universal coefficients theorem and the Kunneth theorem. Thus we deduce that $$\begin{align*} \mathbb{F}_q^* \mathbb{F}_q &\cong \operatorname{Hom}_{\mathbb{F}_p}(\mathbb{F}_q, \mathcal{A}^* \otimes_{\mathbb{F}_p} \mathbb{F}_q) \\ &\cong \bigoplus_{i=1}^n \mathbb{F}_q \otimes_{\mathbb{F}_p} \mathcal{A}^*. \end{align*}$$
One quick check this at least has the correct size is to note that $\mathbb{F}_q \simeq \mathbb{F}_p^{\oplus n}$ as groups (in fact as $\mathbb{F}_p$-modules) and therefore also as spectra, so $\mathbb{F}_q^* \mathbb{F}_q \cong (\mathbb{F}_p^{\oplus n})^* \mathbb{F}_p^{\oplus n}$, which is $n^2$ copies of $\mathbb{F}_p^* \mathbb{F}_p =: \mathcal{A}^*$.