Are all extensions of finite fields cyclic?

I'm not sure that the cyclicity of the unit group of a finite field is being used here. (Not that I have any problem using it: see e.g. Section 2 of these notes for a proof.)

Let $K/\mathbb{F}_q$ be a field extension of degree $n$, so $\# K = q^n$. Let $\sigma: K \rightarrow K$ be $x \mapsto x^q$. Recall:

(Lagrange's Little Theorem): Let $G$ be a finite abelian group of order $n$ and $g \in G$. Then the order of $g$ divides $n$.

The point is that LLT is a special case of Lagrange's Theorem which can be proved by the same argument which proves Fermat's Little Theorem -- i.e., the special case in which $G = \mathbb{F}_p^{\times}$. So one need not talk about cosets and such...

Let $x \in \mathbb{F}_q$. I claim that $x^q = x$. This is clear if $x = 0$, and otherwise apply LLT to $x \in \mathbb{F}_q^{\times}$ to get $x^{q-1} = 1$, which implies $x^q = x$.

Therefore $\sigma$ is an automorphism of $K/\mathbb{F}_q$. As for its order, suppose $\sigma^i$ is equal to the identity: that is, for all $x \in K$, $x^{q^i} = x$. We have $P_i(t) = t^{q^i} - t \in K[t]$ is a polynomial of degree $q^i$ over the field $K$, so by the Root-Factor Theorem (a consequence of the division algorithm for polynomials), $P_i(t)$ has at most $q^i$ roots. It follows that the order of $\sigma$ is equal to $n = \log_q(\# K)$. Thus the cyclic group generated by $\sigma$ is a degree $n$ subgroup of $\operatorname{Aut}(K/\mathbb{F}_q)$. But by basic Galois theory, for an extension $K/F$ of degree $n$, we have $\# \operatorname{Aut}(K/F) \leq n$, with equality holding if and only if $K/F$ is Galois. Therefore $K/\mathbb{F}_q$ is a cyclic Galois extension.

If we like, we can now establish that there is a unique cyclic extension of degree $n$ for any $n \in \mathbb{Z}^+$: we can take the splitting field of $t^{q^n} - t$, and splitting fields exist and are unique up to (nonunique) isomorphism over the ground field.

It seems to me that I have not used the cyclicity of $\mathbb{F}_q^{\times}$ anywhere...

Any finite extension of a finite field $\mathbb{F}_q$ is cyclic. For such an extension $K$ first recall that the Frobenius map $x \mapsto x^q$ is an $\mathbb{F}_q$-linear endomorphism. If $x^q = y^q$ then $(x - y)^q = 0$, hence $x = y$, so the Frobenius map is injective. Since it is an injective linear map from a finite-dimensional vector space to itself, it is surjective, so it is an automorphism. Its fixed field is the subfield of roots of $x^q - x$, which are precisely the elements of the base field $\mathbb{F}_q$. It follows that $K$ is Galois with Galois group the cyclic group generated by $x \mapsto x^q$.

(I guess when I say $\mathbb{F}_q$ I am being mildly circular. Interpret the above proof as follows: any finite extension of $\mathbb{F}_p$ is cyclic, and in fact the above proof shows that they are all of the form $\mathbb{F}_{p^n}$ using the fact that any finite subgroup of the multiplicative group of a field is cyclic, so finite fields $\mathbb{F}_q$ really do have Frobenius maps like I just claimed they do, and then apply the proof again to $\mathbb{F}_q$.)

Below is a complete, noncircular simple proof of the result mentioned by Qiaochu that avoids invoking the high-powered structure theorem for finite abelian groups.

Theorem $\ $ A finite subgroup $\rm\:G\:$ of the multiplicative group of a field is cyclic.

Proof $\ $ The proposition below yields, with $\rm\,m = maxord(G) = expt(G),\,$ that $\rm\, x^m = 1\,$ has $\rm\:\#G\:$ roots. Since a polynomial $\rm\:f\:$ over a field satisfies $\rm\:\#roots\ f \le deg\ f\:$ we infer that $\rm\: \#G \le m.\:$ But maxorder $\rm\:m \le \#G\:$ since $\rm\:g^{\#G} = 1\:$ for all $\rm\:g \in G\:$ (Lagrange). $\:$ Thus $\rm\:m = \#G = maxord(G),\:$ therefore $\rm\:G\:$ has an element of order $\rm\#G,\:$ hence $\rm\:G\:$ is cyclic.

$\begin{eqnarray}\rm{\bf Proposition}\qquad maxord(G) &=&\,\rm expt(G)\ \text{ for a finite abelian group}\ G,\ i.e.\\[.5em] \rm max\ \{ ord(g) : \: g \in G\} &=&\,\rm min\ \{ n>0 : \: g^n = 1\ \ \forall\ g \in G\}\end{eqnarray}$

Proof $\ $ By the lemma below, $\rm\: S\, =\, \{ ord(g) : \:g \in G \}$ is a finite set of naturals closed under$\rm\ lcm$.

Hence every $\rm\ s \in S\:$ is a divisor of the max elt $\rm\: m\ $ [else $\rm\: lcm(s,m) > m\,$],$\ $ so $\rm\ m = expt(G)$.

Lemma $\ $ A finite abelian group $\rm\:G\:$ has an lcm-closed order set, i.e. with $\rm\: o(X) = $ order of $\rm\, X$

$$\rm X,Y \in G\ \Rightarrow\ \exists\ Z \in G:\ o(Z) = lcm(o(X),o(Y))$$

Proof $\ \ $ By induction on $\rm\: o(X)\, o(Y).\ $ If it's $\:1\:$ then trivially $\rm\:Z = 1$. $\ $ Otherwise

write $\rm\,\ o(X)\, =\: AP,\: \ o(Y) = BP',\ \ P'\mid P = p^m > 1,\ $ prime $\rm\: p\:$ coprime to $\rm\: A,B.$

Then $\rm\,\ o(X^P) = A,\ o(Y^{P'}) = B.\ $ By induction there's a $\rm\: Z\:$ with $\rm \: o(Z) = lcm(A,B)$

thus $\rm\, o(X^A Z) = P\ lcm(A,B) = lcm(AP,BP') = lcm(o(X),o(Y)).$