Cantor's Theorem states that for any set $A$ there is no surjective function $A\to\mathcal P(A)$. With $A=\mathbb N$ this implies that $\mathcal P(\mathbb N)$ is not countable.
(But where on earth did you find those nice explanations of countability and power sets that didn't also tell you this?)
Here is a third variation, with some details left for you.
First, to solve your problem, it is enough to show that any subset of $\mathbb{N}$ is countable.
So fix a subset $Y$ of $\mathbb{N}$. You know that $\mathbb{N}_n$ is countable for all $n$, and you have already shown that any subset of a finite set is finite, hence countable. So you may assume that $Y$ is not a subset of $\mathbb{N}_n$ for any $n$, i.e., $Y$ is has no upper bound in $\mathbb{N}$.
Now define $g\colon \mathbb{N}\to Y$ inductively as follows. Let $g(0)=\min Y$. Suppose $g(0),\ldots,g(n)$ have already been defined. Define $g(n+1)=\min(Y\setminus\{g(0),\ldots,g(n)\})$. This minimum exists since $Y$ is not contained in $\{g(0),\ldots,g(n)\}$.
We claim that $g$ is a bijection.
First, $g$ is injective by construction, since we always choose $g(n+1)$ distinct from $g(0),\ldots,g(n)$. Suppose $g$ is not surjective. Define
$$
k=\min \{y\in Y:\text{$y$ is not in the image of $g$}\}.
$$
Let $Z=Y\cap\mathbb{N}_{k-1}$ (i.e., $Z$ is all elements of $Y$ strictly less than $k$). Since $Z$ is finite and all of its elements are in the image of $g$, we can choose some $n$ such that $Z\subseteq\{g(0),\ldots,g(n)\}$. Then $k=\min (Y\setminus\{g(0),\ldots,g(n)\})$. So $k=g(n+1)$ by definition, which contradicts our assumption that $k$ is not in the image of $g$.
Best Answer
The definition of countable is that a set is countable precisely when there is a bijective map from it to a subset of the natural numbers. See for example wikipedia.
Therefore your question is answered immediately by definition.
The more interesting question, which is what I think you really mean to ask, is to show that any countable set is either finite, or there is a bijective correspondence between it and $\mathbb{N}$.
Suppose we have an injective map $f\colon S\to \mathbb{N}$. Suppose that $S$ is not finite. We will construct a bijection $g\colon \mathbb{N}\to S$.
Firstly we describe an inductive process for picking elements $s_0,s_1,s_2,\cdots\in S$.
We know $f(S)$ is not empty, as $S$ is not finite (hence not empty), and given $s\in S$ we have $f(s)\in f(S)$. By the well-ordering principle we may pick $x\in f(S)$ minimal in $f(S)$. As $f$ injective, there is a unique $s_0\in S$ such that $f(s_0)=x$.
Once $s_0,s_1,\cdots,s_{i-1}\in S$ have been selected, we select $s_i\in S$ as follows. The set: $$X_i=\{x\in f(S)| x>f(s_{i-1})\},$$ is non-empty, as otherwise the image of $f$ would be a finite set, so $S$ would be finite. By the well-ordering principle we may pick $x\in X_i$ minimal. As $f$ injective, there is a unique $s_i\in S$ with $f(s_i)=x$.
Now we claim the function $g\colon \mathbb{N}\to S$ mapping $i\mapsto s_i$ is bijective.
Note that by construction, for $i>0$ we have $f(s_i)\in X_i$ so $f(s_i)> f(s_{i-1})$. Then by induction on the size of $j-i$, we have if $j>i$ then $f(s_j)>f(s_i)$. Thus $g$ must be injective.
Now pick an arbitrary $s\in S$. To show that $g$ is surjective, we must show that $s=s_i$ for some $i\in \mathbb{N}$. We know $f(s_i)$ is an increasing sequence, so for some $j\in\mathbb{N}$, we have $f(s)<f(s_{j})$, which is minimal in $X_j$, so $f(s)\notin X_j$.
To complete our proof we will prove by induction that for $j>0$:$$f(S)=\{f(s_0),f(s_1),\cdots,f(s_{j-1})\}\cup X_j$$
Thus we have that $f(s)=f(s_i)$ for some $i<j$ and $s=s_i$.
We selected $f(s_0)$ minimal in $f(S)$, so for every element $x\in f(S)$, either $x=f(s_0)$ or $x>f(s_0)$ so $x\in X_1$:$$f(S)=\{f(s_{0})\}\cup X_1$$
For the inductive step, we need only note that we selected $f(s_{i-1})$ minimal in $X_{i-1}$, so any element of $X_{i-1}$ is either $f(s_{i-1})$, or greater than $f(s_{i-1})$, so lies in $X_i$: $$X_{i-1}=\{f(s_{i-1})\}\cup X_i\qquad\qquad (1)$$ Thus for $i\geq 2$: \begin{eqnarray*}f(S)&=&\{f(s_0),f(s_1),\cdots,f(s_{i-2})\}\cup X_{i-1}\\&=&\{f(s_0),f(s_1),\cdots,f(s_{i-2})\}\cup \{f(s_{i-1})\}\cup X_i\end{eqnarray*} Here the first equality comes from the inductive hypothesis, and the second equality comes from $(1)$.