Two facts:
- The norm is multiplicative: $N(ab) = N(a)N(b)$.
- The nonzero elements of a finite field form a cyclic group (under multiplication).
So, if you can figure out what a generator of the multiplicative field of $\mathbb{F}_{p^k}$ maps to...
Added. Your comment below suggests you are a bit confused. So let me set things up a bit.
Given a field extension $F\subseteq K$ of finite degree, the norm from $K$ to $F$, $N_{K/F}\colon K\to F$ is the map that sends $N(a)$ to the determinant of $L_a\colon K\to K$, the linear transformation from $K$ to $K$ given by multiplication by $a$, considering $K$ as a vector space over $F$. The map is multiplicative, and always takes values in $F$. "Surjectivity" here would refer to surjectivity as a map $N_{K/F}\colon K\to F$.
You are considering $F=\mathbb{F}_{p^k}$, and $K=\mathbb{F}_{p^{kn}}$ for some positive integers $k$ and $n$ (remember that $\mathbb{F}_{p^a}$ is an extension of $\mathbb{F}_{p^b}$ if and only if $b|a$).
Since the multiplicative group of $K$ is cyclic, it is generated by some $a$; so the non-zero part of the image of $N$ is generated by $N(a)$, hence you only need to figure out what $N(a)$ is.
Because the powers of $a$ give all nonzero elements of $K$, then $K=\mathbb{F}_{p^k}(a)$; so $\{1,a,a^2,\ldots,a^{n-1}\}$ is a basis for $K$.
It is pretty easy to figure out what the matrix of $L_a$ is with respect to this basis (it will depend on the minimal polynomial of $a$, though). Then you want to argue that the determinant of this matrix is necessarily a generator of the multiplicative group of $\mathbb{F}_{p^k}$.
For example, with $\mathbb{F}_3(\sqrt{2})$, the multiplicative group is generated by $1+\alpha$, where $\alpha=\sqrt{2}$, since:
$$\begin{align*}
(1+\alpha)^2 &= 1+2\alpha+\alpha^2 = 3+2\alpha = 2\alpha;\\
2\alpha(1+\alpha) &= 2\alpha+4 = 1+2\alpha;\\
(1+2\alpha)(1+\alpha) &= 2;\\
2(1+\alpha) &= 2+2\alpha;\\
(2+2\alpha)(1+\alpha) &= \alpha;\\
\alpha(1+\alpha) &= 2+\alpha;\\
(2+\alpha)(1+\alpha) &= 1.
\end{align*}$$
Note that $\{1,1+\alpha\}$ is a basis for $\mathbb{F}_3(\sqrt{2})$ over $\mathbb{F}_3$. If we let $a=1+\alpha$, then $L_a$ has matrix, relative to this basis, equal to
$$\left(\begin{array}{cc}
0 & 1\\
1 & 2
\end{array}\right)$$
(since $(1+\alpha)^2 = 2\alpha = 1 + 2(1+\alpha)$). So the determinant of this matrix is $-1 = 2$, hence $N(1+\alpha) = 2$, which happens to be a generator of $\mathbb{F}_3^{\times}$. That means that the image of $N$ consists of $0$ plus the subgroup of $\mathbb{F}_3^{\times}$ generated by $N(1+\alpha)=2$, which is all of $\mathbb{F}_3$.
Note that even though $K=\mathbb{F}_3(\sqrt{2})$, $\sqrt{2}$ does not generate the multiplicative group of nonzero elements of $K$; we needed to take a different element.
I think you have a lot of the right stuff written down. Let's take $\alpha$ to be a generator for the cyclic [see Lemma 1.6 here for a proof] group $K^*$, so $\alpha$ has order $q^n - 1$. Then, as you say, its norm is
\[
N_{K/F}(\alpha) = \alpha^{1 + q + \cdots + q^{n - 1}} \in F^*.
\]
This norm generates $F^*$ because its order is precisely $q - 1$. This is just group theory: if an element $x$ in a group has order $mk$ then $x^m$ has order $k$.
You could also focus on the size of the kernel, as Mike B suggests. As Brandon points out, these are the roots of a certain polynomial, which gives you an upper bound. And there is an obvious lower bound.
A very useful generalization of this is Hilbert's Theorem 90.
Best Answer
It is not true for any field of characteristic $p \ne 0$. As noted in the comments, if $K/F$ is not separable, the result can fail.
For your particular case of finite fields, note that we can take $\sigma(x)=x^q$ for all $x \in F$, where $q=|K|$. Then trace($u$) is a polynomial in $u$ of degree $q^{n-1}$ and therefore can't have more than $q^{n-1}$ roots in $F$. But $|F|=q^n$. Thus the trace map is nonzero, hence surjective, and your argument works.