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.
Let $F$ be any field. The compositum of separable extensions of $F$ contained in the algebraic closure $\overline{F}$ of $F$ will itself be separable, and so there is a largest separable extension of $F$ contained in $\overline{F}$ (namely, the compositum of all separable extensions). This is called the separable closure of $F$ in $\overline{F}$. (See for example Lang's Algebra, revised 3rd Edition, Theorem 4.5 and discussion following, pp. 241f).
Now start with a non-perfect field; for example, take $\mathbb{F}_p(x)$, the field of rational functions with coefficients in the field of $p$ elements.
Let $K$ be the separable closure of $F$ as above; because $F$ is not perfect, $K$ cannot equal $\overline{F}$. In particular, $K$ is not algebraically closed.
However, every nontrivial algebraic extension of $K$ is not separable (in fact, it will be purely inseparable): because if $L$ is an algebraic separable extension of $K$, then $L$ is also an algebraic separable extension of $F$, hence must be contained in $K$, so $L=K$.
Thus, no nontrivial algebraic extension of $K$ is separable, so no nontrivial algebraic extension of $K$ is Galois over $K$; and yet there are nontrivial algebraic extensions of $K$, since $K$ is not algebraically closed.
Best Answer
The short answer is that you do not need to view the elements of finite fields as polynomials, but it simply is the most convenient presentation for many a purpose.
The slightly longer answer is that those elements really aren't polynomials, but instead they are cosets in a ring of polynomials, and we simply select the lowest degree polynomial to represent the entire coset. This version of the answer is pedagogically possibly the worst I'm gonna give, but it does come in handy when you do calculations in a finite field in a computer program. Namely, with a bit of care you can use either those low degree polynomials, or you can use monomials to represent the same elements. The former are useful for addition, the latter for multiplication. This is because we can use discrete logarithm tables. I'm not gonna discuss this aspect now, but if you are interested you can take a peek at this Q&A I prepared for referrals like this in mind.
Then the long answer - building up on the explanation given by Mathmo123 (+1).
When working with algebraic extensions of number fields, say $\Bbb{Q}$, students often take comfort in thinking of those extensions as consisting of some explicit numbers. Been there, done that. This works because we can always think of a copy of that extension field inside the field of complex numbers $\Bbb{C}$. This does have some pitfalls (there are often several distinct ways of view the given field as such a subset), but we can do this because A) $\Bbb{C}$ is algebraically closed, B) at that point in our studies the concept of a number is still closely tied to $\Bbb{C}$ and its subsets.
Consider the following. It is certainly more natural to work with $\sqrt2$ rather than the coset $x+\langle x^2-2\rangle$ in the quotient ring $\Bbb{Q}[x]/\langle x^2-2\rangle$. We easily do arithmetic as follows $$ (3+\sqrt2)(5+4\sqrt2)=15+(5+12)\sqrt2+4(\sqrt2)^2=23+17\sqrt2. $$ But notice that we multiplied those numbers involving $\sqrt2$ exactly like we would multiply the polynomials $$ (3+x)(5+4x)=15+17x+4x^2. $$ Only in the end we replaced $x^2$ with $2$. All because we think of $x$ having "value" $x=\sqrt2$. Saying that we here actually did arithmetic with polynomials modulo $x^2-2$ is just a fancy way of saying that we use $\sqrt2$ exactly as we use $x$ except in the end we replace all occurrences of $(\sqrt2)^2$ with $2$.
Building up on this we can similarly do arithmetic with $\root3\of2$. Only this time we can only simplify third powers and higher. So compare (I write $\root3\of 4$ in place of $(\root3\of2)^2$ and similarly for higher powers) $$ \begin{aligned} (1+2\root3\of2+3\root3\of4)(1+\root3\of4)&=1+2\root3\of2+(3+1)\root3\of4+2\root3\of8+3\root3\of{16}\\ &=(1+2\cdot2)+(2+3\cdot2)\root3\of2+4\root3\of4\\ &=5+8\root3\of2+4\root3\of4 \end{aligned} $$ replacing $\root3\of 8$ with $2$ and $\root3\of{16}$ with $2\root3\of2$ (and $\root3\of{32}$ with $2\root3\of4$ should the need arise). This is, again, exactly like working with polynomials $$ (1+2x+3x^2)(1+x^2)=1+2x+(3+1)x^2+2x^3+3x^4, $$ where this time we replaced $x^3$ with $2$ and $x^4$ with $2x$.
What's the deal you may ask? In these two example we could have simply used the real numbers $\sqrt2$ and $\root3\of2$. We might even have tried to use their decimal approximations to do the arithmetic with a pocket calculator. Sure, that would introduce rounding errors whereas doing it as above is precise, because it is easier to identify the numbers exactly. By this I mean, it is in this sense more informative to write $$ (\sqrt2-1)^{100}=94741125149636933417873079920900017937-66992092050551637663438906713182313 772 \sqrt{2} $$ instead of $$ (\sqrt2-1)^{100}=5.2775391806914391296141\cdot10^{-39}, $$ which is what a calculator might give you. For example, from that decimal expansion it is very hard to realize that it actually is a number of the form $a-b\sqrt2$ for some integers $a,b$.
Forward we go. What is you want to do arithmetic with the largest real zero of $x^5-2x^3-2x+2$. Plotting that polynomial shows that this number is slightly bigger than $1.5$. Well, this time we DO NOT HAVE A NICE EXPRESSION FOR THAT NUMBER IN TERMS OF RADICALS. So what to do? Just call the number $\alpha$, do arithmetic with its polynomials as above, and keep in mind that by the defining equation $$ \alpha^5=2\alpha^3+2\alpha-2. $$ Therefore we can calculate for example that $$ \begin{aligned} \alpha^7&=\alpha^2\alpha^5\\ &=\alpha^2(2\alpha^3+2\alpha-2)\\ &=2\alpha^5+2\alpha^3-2\alpha^2\\ &=2(2\alpha^3+2\alpha-2)+2\alpha^3-2\alpha^2\\ &=6\alpha^3-2\alpha^2+4\alpha-4. \end{aligned} $$
What has this got to do with doing arithmetic in finite fields? There the situation is much like in that last case. It is not convenient to use a numerical value for $\alpha$, when we need to do exact arithmetic and avoid rounding errors and such. All we have to work with is that polynomial equation satisfied by $\alpha$. We use that equation to do our arithmetic. The price we need to pay is that $\alpha$ does not have a precise identity. In the above example any of the five zeros of that polynomial - two of them complex numbers - would lead to the same arithmetic. This is because the related fields are isomorphic.
Enough of why polynomials (modulo an equation). You asked for alternatives. Let's look at the field of four elements, denote it $\Bbb{F}_4$ or $GF(4)$, whichever you are more familiar with. The field looks like $$ \Bbb{F}_4=\{0,1,\alpha,\alpha+1\}, $$ and its arithmetic follows from it having characteristic two (so $1+1=0=\alpha+\alpha$) and the special equation $\alpha^2=\alpha+1$.
We can produce $\Bbb{F}_4$ as a quotient ring much the same way that we produce the field of seven elements as $\Bbb{Z}/7\Bbb{Z}$ - residue classes of integers modulo seven. Here's one way. Let $\omega=(-1+i\sqrt3)/2$ be the usual complex primitive third root of unity. Let us look at the ring $$ \Bbb{Z}[\omega]=\{a+b\omega\mid a,b\in\Bbb{Z}\}. $$ We can then reduce modulo two in the ring $\Bbb{Z}[\omega]$. In other words, we can do arithmetic as usual, but do operations with $a,b$ modulo two, so effectively both $a$ and $b$ will have two choices, $0,1$, and we have four combinations of them altogether. What do we get? Because $$ 0=\omega^3-1=(\omega-1)(\omega^2+\omega+1) $$ we can deduce that $$ \omega^2=-\omega-1. $$ Now, if we reduce this modulo two, we see that, because $1\equiv-1\pmod2$, $\omega^2=\omega+1$. In other words $\omega$, or more precisely, its residue class modulo two, takes the role of $\alpha$ in $\Bbb{F}_4$
We can produce any finite field in this way. In infinitely many different ways. But using the resulting representations of complicated numbers with coefficients modulo a prime number does not really help us to do any arithmetic operations. So we just usually won't bother.
This became even longer than I anticipated. Hope it helps :-)