Question: I thought the set of natural number functions would be of the same cardinality as the countably infinite product of $\mathbb{N}$, which is countable.

Each natural number function can be identified with an infinite-tuple of $\mathbb{N}$ by letting the $i$th entry be the image of the number $i$ under the function.

Answer: 
Cantors diagonalisation method: If it is countable then it is $F=\{f\_1,f\_2,\ldots\}$. But the function $g(i):=f\_i(i)+1$ is not in $F$. A contradiction to the initial assumption. 

Proof:

For every $i $ we have
$$g(i)=f\_i (i)+1 \implies g (i)\ne f\_i (i) \implies g \ne f\_i $$
and so $g \notin F$.
The countably infinite product of $\mathbb{N}$ is not countable, I believe, by Cantor's diagonal argument.