$|\{\text{functions } \{0,1\} \to \mathbb{N} \}|= |\mathbb{N}^{\{0,1\}}|= |\mathbb{N}^2|$
Indeed, if you are thinking of $\mathbb{N}^2$ as the set of ordered pairs of natural numbers, then the function
$\varphi: \{\text{functions } \{0,1\} \to \mathbb{N} \} \to \mathbb{N}^2$
defined as $\varphi(f)= (f(0),f(1))$
is a bijection.
It is an injection: if $f\not=g$, then $f(0)\not=g(0)$ or $f(1)\not=g(1)$, hence $\varphi(f)\not= \varphi(g)$.
It is a surjection: given $(m,n)\in \mathbb{N}^2$, define $f:\{0,1\} \to \mathbb{N}$ as $f(0)=m$, $f(1)=n$. Then $\varphi(f)=(m,n)$.
In fact, for some intuition, think that what this bijection is saying is that a function $\{0,1\}\to \mathbb{N}$ is completely determined by a couple of natural numbers. Who could they be but $f(0)$ and $f(1)$? :)
So, now I claim that $|\mathbb{N}^2|=|\mathbb{N}|$. Indeed, it is the cartesian product of two countable sets, and the cartesian product of a finite number of countable sets is countable, hence the set of functions $\{0,1\} \to \mathbb{N}$ is countable, i.e. it is equinumerous to $\mathbb{N}$.
You comment you can't use cardinal arithmetic: a more constructive proof would be to exhibit a bijection. See this question: How does one get the formula for this bijection from $\mathbb{N}\times\mathbb{N}$ onto $\mathbb{N}$? which attacks the problem of showing that $|\mathbb{N}\times \mathbb{N}|=|\mathbb{N}|$ more directly.
ADDED: An obvious generalization of the above leads to the fact that, for $n\in \mathbb{N}$, $|\{\text{functions } \{0,\dots,n-1\} \to \mathbb{N}\}| = |\mathbb{N}^n|$. Having this in mind, now forget you ever defined $\mathbb{N}^k$ for any $k\in \mathbb{N}$. Let's have a different approach.
Let $I$ be any given set. Define $\mathbb{N}^I$ as $$\mathbb{N}^I := \{\text{functions } I \to \mathbb{N}\}$$
This is the usual notation for the set of functions from $I$ to $\mathbb{N}$.
Now, in set theory (Zermelo-Fraenkel), the number $k\in \mathbb{N}$ is defined as the set $\{0,\dots,k-1\}$. So what if we take $I=\{0,\dots,k-1\}$? We have that $$\mathbb{N}^k=\mathbb{N}^{\\{0,\dots,k-1\\}} = \\{\text{functions } \\{0,\dots,k-1\\} \to \mathbb{N}\\}$$
In particular, with $k=2$, we obtain that $\mathbb{N}^2=\{\text{functions } \{0,1\} \to \mathbb{N} \}= \{\text{functions } 2 \to \mathbb{N}\}$. Now the above proof shows that our new $\mathbb{N}^2$ is equinumerous to the set of ordered pairs of natural numbers. This is nice. Why?
Well, first observe that equinumerous sets are indistinguishable from the point of view of set theory (in fancy words: bijections are isomorphisms in Set). So if two sets are equinumerous, there is no harm done with taking any of them as the definition of the set.
Then, observe that this definition is in much bigger generality. We have defined $\mathbb{N}^I$ for any set $I$. With our previous definition, we could only extend the generality for any finite set $I$, namely defining $\mathbb{N}^I$ as the set of $|I|$-uples of natural numbers: this definition makes no sense a priori for infinite $I$.
A final observation: in this final addendum, $\mathbb{N}$ can be taken to be any set, of course.
Best Answer
This is a cool problem and it basically comes down to the countability of the rationals and uncountability of the reals which are both so called "standard" results.
For the former set of functions: $$|\{0,1\}\rightarrow \mathbb{N}| = |\mathbb{N}^2| = |\mathbb{N}|$$
The "intuitive" (I dislike that word) way to see this is to think of maps as tuples in $\mathbb{N}^2$ with each coordinate specifying where either $0$ or $1$ are mapped to. For example $(3,4)$ is the map that takes $0\mapsto 3$ and $1\mapsto 4$. The reason this has the same cardinality as $\mathbb{N}$ is because we can define a one to one map between the two sets (to find this map look up a proof for the countability of the rational numbers).
Now for the latter set of functions (which are far far cooler to think about) $$| \mathbb{N}\rightarrow\{0,1\}| = |2^\mathbb{N}| = |\mathbb{R}|$$
The reason being is that for each $n$ in $\mathbb{N}$ we either map to $0$ or $1$, which means we can represent each of our functions as a binary address (binary number) $$a=0.a_1a_2a_3...$$
Where the $n^{th}$ digit $a_n\in\{0,1\}$ of the binary number $a\in[0,1]$ tells us where $n$ is mapped to. For example the binary number $0.\dot{0}$ is the map that takes everything in $\mathbb{N}$ to $0$ and the binary number $0.\dot{0}\dot{1}$ takes even numbers to $0$ and odd numbers to $1$ (if we take $0\in\mathbb{N}$, otherwise it's the other way round). Now every binary address defines a valid function from the natural numbers to $\{0,1\}$ and hence the carinality of the set of such maps is the cardinality of the real numbers between $0$ and $1$ which is uncountable and equal to $|\mathbb{R}|$. (If you haven't already go check out a proof for the uncountability of the real numbers between $0$ and $1$, it's neat!)