Why are polynomials so useful in mathematics? This is perhaps unanswerable,
or perhaps I am too algebraically ignorant to phrase it cogently, but:

Is there some identifiable reason that polynomials over
  $\mathbb{C}$,
  $\mathbb{R}$, $\mathbb{Q}$, $\mathbb{Z}$, $\mathbb{Z}/n\mathbb{Z}$
  are so pervasively useful in mathematics?

Is it because polynomials are in some sense the most natural functions
defined on a field?
I know that every function over a finite field $\mathbb{F}^n \to \mathbb{F}$ is a polynomial.
And, by the
Stone–Weierstrass theorem,
every continuous function on an interval can be approximated by a polynomial.
Is this the universal aspect of polynomials that
"explains" their ubiquity?
Even tropical polynomials, which employ
alternative addition/multiplication operations
forming a semiring, are proving useful.
I'd appreciate your insights!
 A: Polynomials can be used to extract information about finite sequences much in the same way as generating functions can be used for infinite sequences. However, it is good to note that generating functions are not always more suitable for such purposes than polynomials; polynomials allow more operations and convergence issues can be neglected. In fact, one does even need the underlying field to have any topological structure. 
Let me give some examples where polynomials are more appropriate than generating functions. For example, the  combinatorial nullstellensatz is a useful tool in combinatorics, particularly in additive problems,  and its formulation is based on polynomials over a field. Another important example is that one obtains better results in the Hardy-Littlewood circle method by replacing infinite Fourier series with trigonometric polynomials. Third exmple is that manipulating suitable polynomials in $\mathbb{Z}/p\mathbb{Z}$ gives some interesting reults in number thory, such as Wolstenholme's theorem. Fourth example is that irrationality and transcendence proofs are usually based on considering suitable polynomials (for example, in the case of $\pi$).  
In addition, polynomials sometimes serve as ''generalized integers'' in number theoretical contexts. Many theorems are easier to prove for them (such as Fermat's last theorem for non-constant polynomials), and they can be used to conjecture results about integers; this is how abc conjecture was found, for instance. 
On the other hand, in complex analysis, polynomials are basic examples instead of generalizations. There are numerous results in complex analysis that are easy for polynomials but generalize in an interesting way to analytic functions, and on the other hand, there are also many results where the polynomials are the only exceptions due to their slow growth or rigidness. The fact that polynomials are determined by their values in finitely many points is indeed another reason for their usefulness in analysis and other branches as well. 
A: Polynomials are, essentially by definition, precisely the operations one can write down starting from addition and multiplication. More formally, polynomials with coefficients in a commutative ring $R$ are precisely the morphisms in the Lawvere theory of commutative $R$-algebras. So in some sense caring about polynomials is equivalent to caring about commutative rings and, more generally, commutative algebras. See, for example, this blog post for some details; in particular, that blog post makes precise the assertion that polynomials are not only the most natural but in fact the only natural operations on commutative $R$-algebras. 
A: I suspect the question is not answerable because utility can be subjective and rationalizing
subjective notions leads to more arguments and less elucidation.  However, this gives
me an opportunity to mention a couple aspects of polynomials that deserve more
press.
Polynomials are a generalization of number representation, replacing base 10 or
base 2 by base x, while eliminating carry.  This representation can be used in
forming error correcting codes, in computing transforms, even in speeding
up multiplication of large numbers.  The uses Euler had for determining certain
combinatorial results through manipulating power series could still be obtained
by truncation, so they served as precursors to generating functions.  There are
also polynomial encodings used in various ways in mathematical logic, among
them forms of Goedel numbering and representing certain arithmetical facts
as solutions to certain systems of polynomial equations.
In general algebraic structures, one picks some basic operations and then composes
them to get derived term operations, e.g x+ yxx. Substitute elements for some of
the variables, and one gets polynomial operations of the structure, e.g. x + 3xx.
The set of polynomial operations can be a dense set in a larger set of operations,
and one now turns to representation or approximation of arbitrary functions by
a polynomial operation or by a sequence of such.  Many interesting problems of
representation and approximation are studied, among them circuit optimization and
stability of numerical algorithms.  The fact that polynomials are finite computational units
is our handle on problems that might need infinite amounts of computation to determine precisely.
I guess the answer is that mathematicians like to turn problems into nails, so that they can
use polynomial hammers on them.  If it works, why not?
A: At risk of being overly bold, allow me to suggest:

Polynomials are useful because quadratic polynomials are useful.

If we can all agree that linear algebra is an indispensable tool in mathematics then it's hard to argue with the success of equipping vector spaces with quadratic structures - this is the starting point of nearly all of geometry and large portions of number theory.  Even when we move on to higher degree polynomials or transcendental objects, quadratic structures generally appear as local approximations (how often do you go past the degree 2 term in a Taylor series?)
So the question becomes: why are quadratic polynomials useful?  There seem to be two different but interacting reasons.  The first is that quadratic functions of a real variable are always either convex or concave and therefore have a unique maximum or minimum.  The second is that quadratic functions are intimately related to bilinear forms and therefore can be accessed using linear algebra.  The combination of these two reasons seems to explain the success of quadratic algebra in analysis and geometry (e.g. Hilbert spaces, Riemannian manifolds).  This is also part of the story behind their utility in number theory, though I'm not sure I've completely explained the importance of quadratic structures on finite fields.  (Related issue: why is quadratic algebra over $\mathbb{F}_2$ so fundamental in the topology of manifolds?)
A: On one hand polynomials are defined by the most straightforward operations. One doesn't need to involve inequalities (nor division). In this sense polynomials form a narrow class about which it is easy to prove useful theorems and algorithms. On the other hand, as @JO'R has mentioned in the Question, all continuous functions are approximated by polynomials. Thus this family is in this sense rich and useful in applications.
A: Aside from any philosophical reasons, I think the pragmatic side of it is the reason they are so popular. 


*

*They are easy to compute and deal with. 
a) before computers: differentiation, integration are easy. Also one of reason why Fourier series are popular.
b) after computers: splines

*Most other functions (exponents, trig functions etc) are glorified polynomials, via Taylor series. 

*Sometimes undeserved popularity: how many times have you seen a 15-term polynomial used in a regression equation?
A: Polynomials turn the idea of performing arithmetic operations (a dynamic, procedural notion: performing operations) into a static object of mathematics that can be considered in its own right (a static notion: a list of instructions, or an element of a ring). This can be seen as an early example of reifiction/object-ification in mathematics, which has traditionally been quite useful, viz. the definition of algorithm, the definition of ring, the definition of category and functor, the definition of cardinal+ordinal, etc. These all take what was previously a rough or vague or intuitive or unstated or procedural/dynamic mathematical idea and turn it into a single mathematical object that can then be studied as such. That is, one can study the object in its own right, its relation with other objects of the same or different types, etc. (In particular, turning processes into objects has been quite useful, but this is but one kind of a more general phenomenon.)
Now, why are polynomials specifically so incredibly and widely useful? Perhaps because the thing they are reifying is so basic, namely the arithmetic operations.
A: Mathematicians and all the tools they can use are subject to the laws of physics which impose certain constraints, e.g. that you can only ever perform a finite number of elementary operations. In a universe governed by classical mechanics this is not true, there you could construct a machine whose clock cycle can increase exponentially fast. Such a machine could perform an infinite amount of computations in a finite time. It is because we don't live in such a universe that polynomials are useful to us.
