Strangely enough, this isn't actually true! Ok, so it is true that if you were to go through one by one and label some real numbers with natural number, you would never run out. But the interesting thing comes when you start with the assumption that you have labelled every real number with a natural number. Turns out there's always some left over...
It's only a proof if you take a leap of faith and accept certain things. You could argue that that's how math works, but to me the less axioms we need, the better.
I really love this quote from Wittgenstein:
"Where the nonsense starts is with our habit of thinking of a large number as closer to infinity than a small one".
What you do to compare sizes of sets A and B is, construct a 1:1 function mapping everything in A to something in B and vice versa.
If such a function exists, they're the same cardinality.
It's a little long-winded, but see:
http://en.wikipedia.org/wiki/Cardinal_number
This idea, which seems obvious only in retrospect, is due to Georg Cantor (the guy with the set, and the paradox).