Efficient representation of a given surjective function $\{1 \ldots N\} \rightarrow \{1 \ldots M\}$ when $N \gg M$ More precisely: The input is set of $M$ sets (most likely stored sequentially on disk) that contain partitions of the set $\{1..N\}$. I want to efficiently (as far as memory and time complexity goes) represent this structure. Let's call this hypothetical structure $S$. I need the structure to support just a single function $p : S \times \{1 \ldots N\} \rightarrow \{1 \ldots M\}$.

It's also safe to assume that I will call this function in order, meaning I will be interested first in $p(S, 1)$, then in $p(S,2)$, etc.

I can represent this structure as an array of $N \times \lceil log_2(M)\rceil$ bits, but that seems too memory inefficient when $M$ is small and $N$ is in billions. I have a hunch that perfect-hashing might be of use here.
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.