The 'theorem above' (that 'every real number has a strictly increasing infinite sequence of rational numbers tending to it') offers a little help with a question given in the title: Is there a sequence that has all real numbers as cluster points?
The set $\Bbb Q$ is countably infinite, so there is a sequence $S$ containing all members of $\Bbb Q$. The set is dense in $\Bbb R$ — every open interval contains infinitely many rational numbers, so for every real number $y$ and arbitrarily small positive $\varepsilon$ there is infinitely many terms of $S$ in a neighborhood $(y-\varepsilon, y+\varepsilon)$. So every real $y$ is a cluster point of $S$,
Q.E.D.
Of course, for any $y$ you can find an infinite monotonic subsequence of $S$, which has a limit $y$ – but you don't need a 'subsequence', let alone 'monotonic'. Of course having 'infinitely many terms' in a neghborhood implies some infinite subsequence, but that subsequence is not necessary, 'infinitely many terms' is enough.
Let's use a binary encoding for our way from the top of the tree to a
particular fraction. We encode the starting position and each move to
the right as $\color{red}1$ while a move to the left is $\color{blue}0$. (This leads to the
familiar binary representation of the Calkin-Wilf sequence.)
Now, if we move to the right, we move from $\frac ab$ to
$\frac{a+b}b=\frac ab+1$. If we make $n$ consecutive steps to the
right, we move from $\frac ab$ to $\frac ab+\color{red}n$, i.e. we effectively add
$n$. If we move to the left, we move from $\frac ab$ to $\frac
a{a+b}$, which is the same as $\frac1{1+\frac ba}$. $n$ steps to the
left means moving from $\frac ab$ to $\frac1{\color{blue}n+\frac ba}$.
Now, hopefully this already rings a bell: this will lead to continued
fractions! Let's take as an example $\frac 37$ which, as a continued
fraction, looks like so:
$$ 0 + \frac1{2+\frac13} = [0;2,3] $$
We can view this representation, reading it backwards, as a means to
navigate the tree from the top. To reach $3$, you need three $\color{red}1$s.
(The first one is for the starting point $\frac11$, the other two are
to go from there to $\frac11+\color{red}2$.) To go from $3$ to
$\frac1{\color{blue}2+\frac13}$, you need two $\color{blue}0$s. At that point, you're already
done; the last zero means you don't need to take any more "$\color{red}1$
turns".
Here's another example. $\frac{19}{11}$ is
$$ 1 + \frac1{1+\frac1{2+\frac1{1+\frac12}}} = [1;1,2,1,2] $$
Reading $[1;1,2,1,2]$ backwards translates to two $\color{red}1$s ($\frac{\color{red}2}1$),
one $\color{blue}0$ ($\frac1{\color{blue}1+\frac12}=\frac23$), two $\color{red}1$s ($\frac23 +
\color{red}2=\frac83$), one $\color{blue}0$ ($\frac1{\color{blue}1+\frac38}=\frac8{11}$), and finally one
$\color{red}1$ ($\frac8{11}+\color{red}1=\frac{19}{11}$).
So, to reach any rational number, compute its continued fraction and
read it backwards which'll give you a way to navigate the Calkin-Wilf
tree and find the number, thereby re-creating the number, step by
step, from the continued fraction. This also proves that every
positive rational number actually occurs in the tree.
There's one small catch which is that you obviously must start with
$\color{red}1$s and end with $\color{red}1$s (possibly, as in the first example, with zero
$\color{red}1$s). Which means the continued fraction needs to consists of an odd
number of pieces. This is not a problem, but rather a good thing.
There are exactly two continued fraction representations for each
rational number, and exactly one of them is the one we need. (For
example, $\frac38$ can be written as $[0;2,1,2]$, which won't work,
but also as $[0;2,1,1,1]$, which is what we need.) This proves
uniqueness in the Calkin-Wilf tree.
Best Answer
A common measure of how "complicated" a (reduced) fraction is is the height:
Definition. Let $\frac{r}{s}$ be a rational number, with $\gcd(r,s)=1$. The height of $\frac{r}{s}$ is $\mathrm{ht}\left(\frac{r}{s}\right)=\max\{|r|,|s|\}$.
Among those of the same height, you can order them by comparing the minimum. For those with the same minimum, you can compare values. So one possibility is:
You would get:
1/1, 1/2, 2/1, 1/3, 3/1, 2/3, 3/2, 1/4, 4/1, 3/4, 4/3, 1/5, 5/1, 2/5, 5/2, 3/5, 5/3, 4/5, 5/4, 1/6, 6/1, 5/6, 6/5, ...
Don't know about a closed formula, though.
Note/Clarification: The height is very standard, especially in Diophantine Analysis and Arithmetic Geometry.
I don't know about the rest of the order I present, though it seems like a natural extension (or one could prefer listing larger rationals first in point 3. Inserting the negatives would also allow for several small variations.