Finite extension of fields with no primitive element
Let $F$ be a finite field with $p$ elements. Let $K=F(x,y)$ be the field of rational functions in two indeterminate variables over $F$. Consider the extension of $K$ obtained by adjoining $p$-th roots of $x$ and of $y$. More precisely, let $k$ be an algebraic closure of $K$. In $k$ we can solve the equation $X^p=x$ in the variable $X$. Let $a$ be a solution of this equation; so $a$ is an element of $k$ which satisfies $a^p=x$. Similarly find an element $b$ which satisfies $b^p=y$.
Consider $L=K(a,b)$. $L$ is a finite extension of $K$, of order $p^2 $ as you can check. However there is no element of degree $p^2$ in $L$, and a primitive element would have to have degree $p^2$.
This example is, in a sense, the simplest possible. Separable finite extensions are simple (contain a primitive element), so we must use a non-perfect base field. Also, extensions of degree $p$ are also simple, so we must use $p^2$.
The example given by Alon is not only a finite extension without a primitive element, but it's the simplest example of a substitute for Galois theory when the field extensions are purely inseparable. In the example, the top field is $L = {\mathbf F}_p(a,b)$ and the base field is $L^p = {\mathbf F}_p(a^p,b^p)$, where $a$ and $b$ are algebraically independent. Since the extension $L/L^p$ is purely inseparable, we can't describe the intermediate fields using Galois theory. Jacobson found a way to describe them using Lie algebras of differential operators: fixed points of field automorphisms are replaced by kernels of differential operators.
Theorem (Jacobson). Let $K$ be a field of characteristic $p$ and $\mathrm{Der}(K)$ be the space of derivations $K \rightarrow K$, which is a Lie algebra under the bracket operation on derivations. To each field $F$ lying between $K$ and $K^p$, let $\mathrm{Der}_F(K)$ be the subspace of derivations on $K$ which vanish on $F$ (the $F$-linear derivations on $K$). Then $\mathrm{Der}_F(K)$ is a restricted Lie subalgebra of $\mathrm{Der}(K)$ (the label "restricted" means the $p$th power of each element in the subalgebra is also in there). If $[K:F]$ is finite then $\mathrm{Der}_F(K)$ is finite-dimensional as a (left) $F$-vector space. Sending $F$ to $\mathrm{Der}_F(K)$ is an inclusion-reversing bijection from the fields between $K$ and $K^p$ over which $K$ is finite-dimensional and the restricted Lie subalgebras of $\mathrm{Der}_F(K)$ which are finite-dimensional over $K$, with $[K:F] = p^{\dim_K(\mathrm{Der}_F(K))}$. The inverse map associates to any restricted Lie subalgebra of $\mathrm{Der}(K)$ which is finite-dimensional over $K$ the elements of $K$ on which the entire subalgebra vanishes.
Let's see how this theorem manifests itself in the example $K = \mathbf{F}_p(u,v)$, where $u$ and $v$ are algebraically independent. Here $K^p = \mathbf{F}_p(u^p,v^p)$ and $[K:K^p] = p^2$. (In other examples, $[K:K^p]$ could be infinite.) The partial derivative operators $\partial_u = \partial/\partial u$ and $\partial_v = \partial/\partial v$ are a basis for $\mathrm{Der}(K)$ as a left $K$-vector space: $$ \mathrm{Der}(K) = K\partial_u + K\partial_v. $$ An example of a field between $K$ and $K^p$ is $K^p(u^m + v^n)$ for positive integers $m$ and $n$. If $m$ and $n$ are both multiples of $p$ then $K^p(u^m + v^n) = K^p$, which is dull and all derivations are 0 on it: it corresponds to $\mathrm{Der}(K) = \mathrm{Der}_{K^p}(K)$. If at least one of $m$ or $n$ is not a multiple of $p$ then the set of derivations that vanish on $K^p(u^m + v^n)$ is $K(nv^{n-1}\partial_u - mu^{m-1}\partial_v)$. If we insist now that $m$ and $n$ are both not multiples of $p$, then changing $m$ or $n$ changes that line of derivations, so the corresponding fields $K^p(u^m+v^n)$ are not the same (you don't need Jacobson's bijection to see that: if one field is killed by a certain differential operator and another isn't, they are not the same field).
We haven't seen the restricted Lie algebra aspect playing an essential role here. In fact all one-dimensional $K$-subspaces of this two-dimensional space $\mathrm{Der}(K)$ are restricted. To see this, pick a one-dimensional $K$-subspace $K\delta$ in $\mathrm{Der}(K)$. Set $F$ to be the common kernel of the operators in $K\delta$, which is just the same thing as $\ker(\delta)$, so $F$ is a field between $K$ and $K^p$.
Clearly
$$
K\delta \subset \mathrm{Der}_F(K) \subset \mathrm{Der}(K)
$$
and the top space is 2-dimensional over $K$. Thus $\mathrm{Der}_F(K)$ is either $K\delta$ or $\mathrm{Der}(K)$. If $K\delta = \mathrm{Der}_F(K)$ then $K\delta$ is restricted since the space of derivations on $K$ vanishing on a subfield is restricted and then we're done. So assume instead that $K\delta \not= \mathrm{Der}_F(K)$, and then for dimensional reasons we must have $\mathrm{Der}_F(K) = \mathrm{Der}(K)$, which by Jacobson's correspondence implies $F = K^p$, so $\ker(\delta) = K^p$. But this is impossible: any nonzero $\delta$ in $\mathrm{Der}(K)$ is nonvanishing at either $u$ or $v$ (if $\delta(u) = 0$ and $\delta(v) = 0$ then $\delta$ vanishes on $K^p(u,v) = K$), so $\ker(\delta)$ is not $K^p$ and thus we have a contradiction, which wraps up this little argument.
That all 1-dimensional $K$-subspaces of $\mathrm{Der}(K)$ in this particular example are restricted Lie subalgebras sounds analogous to the fact that all one-dimensional subspaces of a Lie algebra are Lie subalgebras, although note $\mathrm{Der}(K)$ is not a Lie algebra over $K$, only over $K^p$. Still, if anyone who knows about restricted Lie algebras can indicate in a comment if there is some general theorem about certain subspaces automatically being restricted subspaces, please speak up.
It is a theorem of Gerstenhaber (1964) that the Lie algebra aspect in Jacobson's theorem is always automatic from the restricted aspect: for any field $K$ of characteristic $p$, any $K$-subspace of $\mathrm{Der}(K)$ which is closed under $p$th powers is closed under the Lie bracket on derivations.
This approach to a Galois theory for inseparable extensions has been extended to the case of inseparable $K/F$ where $K^{p^r} \subset F$ some some $r > 1$, using higher derivations. See "Higher derivation Galois theory of inseparable extensions" pp. 187--220 of Handbook [sic] of Algebra, Volume 1. (An account just of Jacobson's case $r = 1$ is in his Basic Algebra II, and in somewhat more detail -- including Gerstenhaber's result -- in Chapter 4 of Karpilovsky's Topics in Field Theory.)
New topic! RK asked, as a comment to Alon's answer, if there is a finite extension of $\mathbf F_p(x)$ which is not primitive. No.
Theorem: If $K$ is a field of characteristic $p$ such that $[K:K^p] = p$, then every finite extension of $K$ has a primitive element.
We can apply this theorem to any rational function field over a perfect field of characteristic $p$. The conclusion of the theorem is stable under passage to finite extensions, so it applies to any function field over a perfect field of characteristic $p$.
Proof: Let $L/K$ be a finite extension. From the hypothesis that $[K:K^p] = p$, $[K:K^{p^m}] = p^m$ for all $m \geq 0$. Then $[K^{1/p^m}:K] = p^m$, so if $K^{1/p^m} \subset L$ we get $p^m|[L:K]$, which means $m$ is bounded. Taking $m\geq 0$ maximal such that $K^{1/p^m} \subset L$, it can be shown that $L/K^{1/p^m}$ is separable.
Let $F$ be any field such that $K \subset F \subset L$. Letting $n \geq 0$ be maximal such that $K^{1/p^n} \subset F$, we have $n \leq m$ and $F/K^{1/p^n}$ is separable. Thus every field between $K$ and $L$ is a separable extension of one of the finitely many fields $K^{1/p^n}$ for $n = 0,1,\dots,m$. Note the tower $F \supset K^{1/p^n} \supset K$, which is a separable extension on top of a purely inseparable extension, is backwards compared to what general field theory tells us: any finite extension can be expressed as a purely inseparable extension on top of a separable extension. We will now bring in that general field theory point of view, in a more precise form.
Any finite extension of fields admits a maximal separable subextension (containing all other separable extensions of the base field in the top field). Moreover, a separable extension of fields has only finitely many intermediate fields (say, by Galois theory). Therefore each $K^{1/p^n}$, for $n = 0,1,\dots,m$ has only finitely many separable extensions inside $L$. Since every field between $K$ and $L$ is a separable extension of $K^{1/p^n}$ for some $n$ from 0 to $m$, there are only finitely many fields between $K$ and $L$. Therefore by Steinitz's theorem on primitive elements, $L$ is a primitive extension of $K$.
QED
In case people are interested, here's a simple proof that there are infinitely many distinct sub-extensions. (This Lang-problem drove me out of my gourd for a few hours recently.)
Okay, so let $k=F_p$. We want to show that
$k(a,b)$ has infinitely many subextensions over $k(x,y)$. where $a=x^{\frac1p}$ and $y=b^\frac1p$
I claim that the extensions given by adjoining $a^m+b^m$, where $m \equiv 1 \text{mod} p$, are different for different $m$. It's enough to show that for any such $m$ and $n$, adjoining both $a^m+b^m$ and $a^n+b^n$ gives $k(a,b)$.
So suppose $m=n+pr$. Then $(a^n+b^n) * (a^p)^r = a^m + b^n*(a^{pr})$. Subtracting from the other one, we get: $(b^m - b^n) * a^{pr} = b^n * (b^{pr} - a^{pr})$
But $b^{pr} - a^{pr}$ is in the base field (each of $b^p$ and $a^p$ is), so we can invert it and get $b^n$ and thus $b$ ($n$ is congruent to 1 mod $p$)!