Efficient representation of a given surjective function $\{1 \ldots N\} \rightarrow \{1 \ldots M\}$ when $N \gg M$
You can reduce your $N \lceil \log_2 M \rceil$ bits to $\lceil N \log_2 M\rceil$ by using Dodis et al's "Changing Base without Losing Space".

I don't think you're going to get much smaller than $N \log_2 M$ bits. For $N \gg M$, many functions will be surjective. In particular, there are $\{{N \atop M}\}$ surjective functions, which is at least $M^{N-M}$.
Thus, at least $\log_2 \left(M^{N-M}\right) = N \log_2 M - M \log_2 M \in \Omega(N \log_2 M)$ bits must be used to represent one, on average.