Q:

When and what was the first proof $\mathbb{Q}$ is countable?

It seems the history of the interesting fact that there is no bijection between $\mathbb{N}$ and $\mathbb{R}$, Cantor's diagonalization trick in the mid 1800s, is common knowledge. Meanwhile, there are dozen(s) of clever proofs of the equally interesting fact that there is a bijection between $\mathbb{N}$ and $\mathbb{Q}$, but which proof was first and what was the story behind it? 

A:

From the Wikipedia article cited by Michael Hardy:

On November 29, 1873, Cantor asked Dedekind whether the collection of positive integers and the collection of positive real numbers "can be corresponded so that each individual of one collection corresponds to one and only one individual of the other?" Cantor added that collections having such a correspondence include the collection of positive rational numbers, and collections of the form $(a_{n_1, n_2, \ldots , n_ν})$ where $n_1, n_2, \ldots , n_ν$, and $ν$ are positive integers.

That tells you when, and given the juxtaposition with the last assertion together with his published proof that the algebraic numbers are countable, I think you can infer how the proof he had in mind probably went. (Define the height of a positive fraction $\frac{p}{q}$ written in lowest terms to be the number $p + q$, observe that there are only finitely many fractions of a given height, and enumerate by height.)

