Is induction something we take on faith? I understand that in mathematics and logic we can continue to reduce things to simpler axioms, principles, and so on, and we have to "stop" at some point otherwise we're just going on forever. We eventually say that some axiom or principle is good enough, so that we accept it to be valid, true, useful, sensible, and so on.

That being said, my question is whether mathematical induction is one of these "fundamental" concepts we just accept, or if it follows from some even deeper or simpler concept.

Sometimes I see people say that it works because of the well-ordering principle of the natural numbers, but this doesn't satisfy me. In Tao's Analysis Vol I, we say $m \leq n$ (for natural numbers $m$ and $n$) iff $m = n + a$ for some natural number $a$. But then if I wanted to prove that any arbitrary set of natural numbers has a "least element" (the definition of the well-ordering principle), I'd be resorting to induction, the very thing I'm trying to "prove."

Does this mean the concept of induction is just something we all accept as one of those sufficiently simple, intuitive things that require no further proof, that comes from no simpler means?
My viewpoint is the same as in Noah's first comment: for me, induction is part of the essence of what I mean when I talk about the natural numbers, so the thing I take on faith is not that induction is true but that the natural numbers "exist," whatever that means. Axioms don't tell you what to take on faith: they're a way for two people to agree that they're talking about the same thing. 

Some people called ultrafinitists would in some sense deny that the natural numbers exist. 

Here is a blog post which describes in detail the sense in which the Peano axioms are a way for two people to agree that they mean the same thing by "the natural numbers."
In the first several books of Aristotle you can find a discussion of different forms of "priority". Among them is a statement concerning priority of existence. In this account, Aristotle remarks that there must exist one individual if, in fact, two individuals are the subject of discussion. It is this account of relation which seems to ground the directionality of succession in natural numbers.

But, the situation is far more complicated. In the same discussion, Aristotle speaks of genera being prior to species. This is a motivation for arriving at the identity of indiscernibles -- a principle denied by first-order logic. Yet, it remains relevant in the guise of the principle of indiscernibility of non-existents from negative free logic. As Dana Scott has observed, this principle grounds Frege's definition of the number zero. Since Frege's definition is essentially that found in Zermelo-Fraenkel set theory, it serves as a condition of well-fomedness for the iterative hierarchy.

A good example in the literature can be found in Moschovakis' work on formal recursion theory where all meaningless syntactic forms are set equal to one another and denoted as the empty partial function.

The reason for mentioning the two directions (from below with succession and from above with "least" classes) is that this accounts for the difference between first-order and second-order notions of induction. The first-order account depends upon a well-formedness condition to assert the individuality of its base element. Note, however, that such a  claim is opaque to formalist accounts of foundations based on formal systems and interpretations.

At a much deeper level, there is the issue of discernibility within a logical domain. Hilbert acknowledges that well formed identity relations are a presupposition of formalist mathematics. So, it is difficult to find relevant discussion. One place to find such considerations is in Russell's "Principles of Mathematics". He distinguishes between being and existence. Then he makes the claim that all things with being can be counted. This is motivated by the logical problem of negative existentials. But it is also a well ordering principle.

In other words, Russell is suggesting that ordinal numbers may be  viewed as generic names for a consistent global labeling for any logical domain. This is implicit in his distinction between a logical class and a mathematical collection. And, it is very nearly explicit in the quote from Bolzano he uses to explain his account of numerical conjunction as the ground of logical domains. Bolzano is clear that each object be denoted uniquely.

Today one speaks of expanding a language with constants so that each object of the domain has a denotation. The procedure is attributed to Abraham Robinson. Such expansions are usually represented using ordinal subscripting.

If you wish to get a sense of how induction arises naturally in mathematical discourse, look at the first four chapters of Moschovakis' book, "Elementary Induction Over Abstract Structures".