Such a polynomial has clearly not degree $0$ and it cannot be of degree two except for $x\longmapsto (\alpha(x))^2$ for $\alpha$ an affine bijection of a field of characteristic $2$.

Are there many examples of degree $3$ (except for the stupid $x\longmapsto (\alpha(x))^3$ with $\alpha$ an affine bijection of a field of characteristic $3$)?

I guess that the degrees of such polynomials (except for affine bijections and their composition with the Frobenius map) are generically fairly high (the interpolation polynomial for a "random" permutation of a finite field with $q$ elements should typically be of degree $q-1$).

What can for instance be said on the smallest degree $>1$ of a non-affine polynomial inducing a bijection of $\mathbb Z/p\mathbb Z$?

nis coprime toq-1, then every element ofKadmits ann-th root inK, so that the polynomial $x^n$ is one-to-one. – damiano May 17 '10 at 13:44