What axiom(s) do I need to prove that every nonempty set of natural numbers has a smallest element? Math people:
The title is the question.  I am not a logician, and to me, it seems self-evident that any nonempty set of natural numbers has a smallest element.  I am reading an analysis book that uses the Completeness Axiom of the real numbers to prove this "fact" (I put "fact" in quotes because a logician might not accept something so obvious as a fact but might require that I assume some axiom).  To me, this really seems like overkill, and that you should be able to prove it using something much weaker.
EDIT: I am not asking specifically about axioms of ZFC.  My question does not even mention ZFC.  I highly doubt that Choice is necessary here and I suspect it may not even be helpful.  I would like (i) confirmation that using the Completeness Axiom of the real numbers to prove that every nonempty set of natural numbers has a least element is massive overkill and (ii) some weaker axioms that give me the same conclusion, the weaker the better.   
 A: Most people, logicians included, will indeed agree that intuitively the claim that every non-empty subset of the natural numbers has a least element (which is knows as the well-ordering principle of the naturals) is self-evident. Another such self-evident property of the natural numbers is the principle of induction. 
As is often the case with self-evident things, actually proving them can be tricky. It turns out (and it's not hard to prove directly) that the well-ordering of the naturals is equivalent to the principle of induction (which is a second order principle). 
Now things become more complicated when one realizes that there exist first order models of arithmetic in which all of the Peano axioms hold as well as all the induction scheme axioms (that is, one axiom per first order formula) in which the second order principle of induction fails. That means that in such models of the naturals the well-ordering principle fails too. So things are not so simple, or self-evident, after all.
I do agree that using the completeness of the reals in order to prove the well-ordering of the naturals is a bit of an over kill as the former is less intuitively clear than the latter. But, it is instructive to see that imposing completeness on the reals (a second order property again) forces the naturals to obey the principle of induction.  
A: The standard ordering on $\mathbb{N}$ is a well-ordering (the well-ordering principle); this is equivalent to the axiom of induction, which is one of the axioms of Peano arithmetic.
Proving that every bounded set of real numbers has a greatest lower bound does require the completeness axiom.
A: One reason this question is a bit tricky to answer is the following: either you are working with the natural numbers directly, and then induction, or equivalently well-ordering, are basic properties that you might well take as axioms.  Otherwise, the natural numbers are appearing as a subset of some other set, and then it's not so clear what other contexts there are that are simpler than $\mathbb N$ considered as a subset of $\mathbb R$.
That being said, here is one axiom that might suit you (although depending on your view-point it might be circular): there are only finitely many natural numbers less than any given natural number.  (The circularity might enter if you adopt certain definitions of finite.)  
This implies well-ordering, i.e. the existence of a least element for any non-empty subset of $\mathbb N$: if $S \subset \mathbb N$ is non-empty, we can choose $n \in S$.  If $n$ is a least element, we are done; otherwise, there are only finitely many elements of $S$ that are less than $n$, and since the ordering on $\mathbb N$ is total, we can find a least element of $S$ among them. 
A: One can use the Induction Principle in order to prove the well ordering principle (that states that every non empty set of natural numbers has a smallest element). For example, you can see T. M. Apostol, Calculus (Volume I), theorem I.37 (well ordering principle) and paragraph I.45 (proof, starting from induction principle). The arguement is by contradiction.
A: Assume that for all natural numbers "a", (a+0)=a.  With both assumptions in place, it follows that (0+0)=0.  No other natural number has the property that (x+x)=x.  Thus, 0 comes as unique.  Addition comes as monotonically increasing.  That is, 
For all x, for all y belonging to the set of natural numbers
 If x<y, then (c+x)<(c+y), where c indicates any constant.

 Also, if (c+x)<(c+y), then x<y.

Now suppose that x=0.  By the second statement, it follows that
 if (c+0)<(c+y), then 0<y.

"y" qualifies as an arbitrary natural number, so 0 comes as the least natural number.  That gives us a "hint".
Now consider any arbitrary set of natural numbers.  Define a monotonicity relation for a function $ on that arbitrary set such that
 if (c $ x)<(c $ y), then x<y.  And if x<y, then (c $ x) < (c $ y)

Define another function # such that there exists some element j belonging to the arbitrary set of natural numbers such that for all x, (j # x)=j.  It follows that (j # j)=j.  Now consider the statement
 if (c $ j)<(c $ y), then j<y.  

Since y came as arbitrary, j comes as the least element of the set.  Since the set came as arbitrary it holds for all subsets of natural numbers.
