Kepler devised a method to enumerate the rational numbers between 0 and 1. This clip from his Harmonices Mundi illustrates the method.
It works like this: Let $m=n=1$. Then $\tfrac{m}{n}$ is the first rational number. The next two are $\tfrac{m}{m+n}$ and $\tfrac{n}{m+n}$. These last two rationals become $m$ and $n$ for the next iteration. Wash, rinse, repeat for eternity. Done.
If we read Kepler's diagram left to right; down to up, the first 10 rationals are:
Suppose we want to know where, say, $\tfrac{6067}{9000}$ appears on that list. We could systematically run through Kepler's tree. Eventually the process will terminate.
But is there a better way to do this? Is there some function that maps each element of $\mathbb{Q}$ between 0 and 1 to $\mathbb{N}$?
EDIT: I'd like to specify that I'd like to know what that function is. I'd like to be able to plug in, say, $\tfrac{3}{8}$, and get the number $10$.
Yes. Just define $f(\frac{p}{q})=42$.
But maybe you want an injective map. Then you can use $f(\frac{p}{q})=q^2 + p$.
Surjective: $f(p/q)=q$
Bijective is more difficult. You've presented one possibility already, but it sounds like you're looking for functions that are easier to compute. But maybe Kepler's function is easier to compute than you think. Let's say we're given the fraction (in lowest terms) $p/q$. We know that $p<q$. So $r = q-p$ is a positive number. Now one of $p/r$ or $r/p$ will be less than 1, whichever one that is, we rename it to $p'/q'$. We also know that $p/q = p / (p+r)$. So in the binary tree above, $p'/q'$ will be the fraction just above $p/q$. Then we repeat, starting from $p'/q'$ this time. A little bit of extra bookkeeping will tell us exactly which branch of the binary tree of fractions we're on, and from that we can compute our natural number output.
If you're observant, you'll notice that this algorithm is pretty much just Euclid's algorithm with extra steps. And Euclid's algorithm is fast.