$|\{\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.
Yes, it would. If $A$ and $B$ had the same cardinality, there would by definition by a bijection (and therefore an injection) $f:B\to A$. It follows immediately that if there is no such injection, then $|A|\ne|B|$.
Thus, if you have an injection from $A$ to $B$, then either there is an injection from $B$ to $A$, in which case $|A|=|B|$ by the Cantor-Schröder-Bernstein theorem, or there is no injection from $B$ to $A$, in which case $|A|<|B|$.
In your specific problem there are fairly obvious injections from $A$ to $B$ and to $C$. It is possible to find an injection from $B$ to $A$ directly, but that is not how I would approach the problem. I would (1) note that for each $n$ there is a bijection between the polynomials of degree $n$ and $\Bbb R^{n+1}$; (2) find a bijection between $\Bbb R$ and $\Bbb R^2$; (3) show by induction that $|\Bbb R^n|=|\Bbb R|$ for $n\in\Bbb Z^+$; and (4) use this to show that $|B|=|\Bbb N\times\Bbb R|=|\Bbb R|$. Depending on how much I had already proved about cardinalities, I could skip some of these steps.
I would not that there is an easy bijection between $C$ and $\wp(\Bbb R)$ and apply Cantor’s theorem to deal with $C$.
Best Answer
I don't know what $C$ means in your question. Also I don't think composing with $x^2$ will work because this is not injective.
Instead you can argue as follows:
First, prove (unless you already know) that the there is a bijection $b:\mathbb{R}\rightarrow[0,\infty]$.
Then let $f\in S$ and consider $f|_{[0,\infty]}$ this is a map from $[0,\infty]\rightarrow\mathbb{R}$. Now compose this function with $b$ you get a map $$\mathbb{R} \overset{b}{\longrightarrow}[0,\infty]\overset{f|_{[0,\infty]}}{{\longrightarrow}\mathbb{R}}$$
Call this map $\varphi:S\rightarrow \mathbb{R}^\mathbb{R}$ where $\mathbb{R}^\mathbb{R}$ denotes the set of functions from $\mathbb{R}\rightarrow\mathbb{R}$.
It is left to show that $\varphi$ is a bijection.
It is 1:1, for if $f,g\in S$ such that $\varphi(f)=\varphi(g)$ then $f,g$ agree on $[0,\infty]$ but since $f(-x)=f(x)$ and $g(-x)=g(x)$ you have that $f=g$.
It is onto, for if $f:\mathbb{R}\rightarrow\mathbb{R}$ we can compose $f$ with $b^{-1}$ to get a map from $[0,\infty]\rightarrow \mathbb{R}$ (first apply $b^{-1}$ and then $f$) applying $\varphi$ on this map we will get $f$ again. In other words $f$ is in the range of $\varphi$ and so it is also onto.