How many subsets of $\mathbb{N}$ have the same cardinality as $\mathbb{N}$?
One can write a bijection between $\mathrm{Fin}(\mathbb N)$ and $\mathbb N$, i.e. between the set of finite subsets of $\mathbb N$ and $\mathbb N$. For example: $$f(A)=\sum_{i\in A}2^i$$
Note that $A$ is finite so this is a well-defined function. It turns out that this is a bijection as well.
Then one can show that $\mathcal P(\mathbb N)\setminus\mathrm{Fin}(\mathbb N)$ is uncountable, and in fact equipotent to $\mathcal P(\mathbb N)$. This is because $k+\aleph_0=2^{\aleph_0}$ implies that $k=2^{\aleph_0}$. So if $k=|\mathcal P(\mathbb N)\setminus\mathrm{Fin}(\mathbb N)|$ then $k=2^{\aleph_0}=|\mathcal P(\mathbb N)|$.
To the second question, one can show that there are $2^{\aleph_0}$ permutations of $\mathbb N$. Therefore if $f\colon A\to\mathbb N$ is a bijection composing it with a permutation of $\mathbb N$ will result in another bijection. It is not hard to show that if we compose different permutations we have different bijections (i.e. they disagree on the value of some point in $A$). Therefore there are $2^{\aleph_0}$ many bijections between any two countable sets.
(I should also remarked that none of the points in this answer requires the axiom of choice.)
$\Bbb N$ has only countably many finite subsets, but it has uncountably many subsets altogether, so it must have uncountably many countably infinite subsets (i.e., subsets with the same cardinality as $\Bbb N$ itself).
If $A$ is any countably infinite set, there are uncountably many bijections between $\Bbb N$ and $A$.
Some more answers:
There are uncountably many sets of odd numbers, and adjoining the even numbers to each of these yields a set with the same cardinality as $\mathbb N$.
Given any real number $x$, we can form the set $S(x)=\{\lfloor x \rfloor,\lfloor 10x \rfloor,\lfloor 100x\rfloor,\dots\}$ (e.g., $S(\pi)=\{3,31,314,3141,31415,\dots\}$), which clearly has the same cardinality as $\mathbb N$, and the map $S$ is a bijection, so this process yields uncountably many sets.
(Really the same as the last one) Given any infinite sequence $(a_n)$ of natural numbers, we can form the set $\{2^{a_1},3^{a_2},5^{a_3},\dots\}$ which has the same cardinality as $\mathbb N$.