The cartesian product $\mathbb{N} \times \mathbb{N}$ is countable

Your intuition is correct. We use the fundamental theorem of arithmetic, namely the prime factorization is unique (up to order, of course).

First we prove injectivity:

Suppose $(k_n,l_n),(k_m,l_m)\in\mathbb N\times\mathbb N$ and $2^{k_n - 1} (2 l_n - 1 ) = 2^{k_m - 1} (2 l_m - 1)$.

$2$ is a prime number and $2t-1$ is odd for all $t$, and so we have that the power of $2$ is the same on both sides of the equation, and it is exactly $k_n=k_m$.

Divide by $2^{k_n}$ and therefore $2l_n-1 = 2l_m-1$, add $1$ and divide by $2$, so $(k_n,l_n)=(k_m,l_m)$ and therefore this mapping is injective.

Surjectivity it is even simpler, take $(k,l)\in\mathbb N\times\mathbb N$ and let $n=2^{k-1}(2l-1)$. Now $n\mapsto(k,l)$, because $2l-1$ is odd, so the powers of $2$ in the prime decomposition of $n$ are exactly $k-1$, and from there $l$ is determined to be our $l$. (If you look closely, this is exactly the same argument for injectivity only applied "backwards", which is a trait many of the proofs of this kind has)

---

As for simpler proofs, there are infinitely many... from the Cantor's pairing function ($(n,m)\mapsto\frac{(n+m)(n+m+1)}{2}+n$), to Cantor-Bernstein arguments by $(n,m)\mapsto 2^n3^m$ and $k\mapsto (k,k)$ for the injective functions. I like this function, though. I will try to remember it and use it next time I teach someone such proof.

It is possible that the notation is getting in the way of seeing what's going on.

Every positive integer $n$ is a power of $2$ times an odd number. (Note that $2^0$ is a power of $2$.)

For example, $840=2^3 \times 105$ and $747=2^0 \times 747$.

In symbols, $$n=2^e \times a$$ where $e$ is a non-negative integer, and $a$ is an odd positive integer.

Moreover, the above representation is unique: If we know $e$ and $a$, we know $n$, and if we know $n$, we know $e$ and $a$.

Since $a$ is odd, it is of the form $2b+1$, where $b$ is a non-negative integer. As $a$ ranges over the odd positive integers, $b$ ranges over the non-negative integers.

Let $f$ be the function that takes $n$ to the ordered pair $(e,b)$. For example, since $840=2^3 \times 105$, we have $f(840)=(3,52)$. Similarly, $f(747)=(0,373)$.

Let $\mathbb{N}_0$ be the set of non-negative integers. Then $f$ is a bijective map from $\mathbb{N}$ to $\mathbb{N}_0 \times \mathbb{N}_0$. This is an immediate consequence of the fact that if we know $e$ and $b$, we know $n$, and conversely that if we know $n$, we know $e$ and $b$.

Not exactly what are looking for, but awfully close! And easy to fix, since $\mathbb{N}$ is just $\mathbb{N}_0$ pushed forward by $1$.

All we need to do is to map $n$ to $(e+1, b+1)$.