What actually is a polynomial?
A polynomial (in one variable) is an expression of the form $$ p(x) = a_0+a_1x+a_2x^2+\ldots+a_nx^n$$ where the coefficients $a_i$ are some kind of number (or more generally they're elements of a Ring). The exponents $1,2,\ldots n$ must all be integers.
Unless we've been silly and $a_n=0,$ $n$ is called the degree of the polynomial. We can formalize this by defining the largest $n$ such that $a_n\ne0$ as the degree.
Notice that constants are allowed. $p(x) = 3$ is a zero-th degree polynomial.
You asked about zero. Yes, $p(x) =0$ is considered to be a polynomial. However, you'll notice that there is a problem with the definition of degree here since there is no coefficient that is nonzero. The degree of the zero polynomial is thus undefined.
This allows us to say that if we multiply two polynomials $w(x)=p(x)q(x)$ with $p$ of degree $n$ and $q$ of degree $m,$ then $w$ has degree $n+m.$ (Notice how the zero polynomial would mess this up if its degree were defined to be zero like the other constants.)
You're right that simplification is important. The $x$ is just a symbol and we can always "combine like terms" $$ a_lx^l+b_lx^l= (a_l+b_l)x^l.$$ We always combine all the terms together and simplify in order to get an expression into the form above with only one term for each power before we do things like consider the degree.
Notice we can add two polynomials according to the simplification rule and get a polynomial as a result. This is a good reason to consider zero to be a polynomial... it allows the sum of two polynomials to always be a polynomial. Likewise we can multiply two polynomials according to the the distributive property, the rule $$ (a_mx^m)(a_lx^l) = a_ma_l x^{m+l},$$ and the additive simplification rule. The result will be another polynomial.
Yes, the exponents all need to be positive. Of course other expressions are possible but they aren't called polynomials. Terms like $x^{-3}$ are considered part of the family of rational functions (or as a commenter noted, the Laurent polynomials, not to be confused with the (unqualified) polynomials). This is just a definition and thus somewhat arbitrary (though good definitions are important for organization). It's just like saying $-4$ is an integer but not a natural number. It's true by definition, and yes, a bit arbitrary, but nonetheless useful and a nearly universal convention.
EDIT As Paul Sinclair pointed out in the comments, there are also polynomials in multiple variables. For instance $$p(x,y) = A + Bx + Cy +Dx^2+Exy+Fy^2$$ is the general degree two polynomial in two variables. The degree of a term is just the sum of the degrees with respect to the individual variables. So a term like $3xy$ has degree two and a term like $3x^4y^5z$ would have degree $4+5+1=10.$ The degree of a polynomial is the degree of its highest-degree term with nonzero coefficient.
There are lots of good answers here and they are all essentially correct, even though they are different! I will try to contribute another, which is somewhat more abstract than the others. I normally wouldn't try this for a high school student, but your very good question deserves different kinds of answers. Maybe this one will help.
It's the "what actually is" in your question that I want to address. In mathematics at a more advanced level you don't think as much about what something "is" as you do about how it "behaves". (The same is true in object oriented programming languages = you say you're studying computer science. If you're learning Java you know about this.)
To manipulate polynomials (which you know how to do) all you really need to know is the sequence of coefficients. We'll assume for the moment that those coefficients are ordinary numbers. It's useful to start those coefficients with the constant term. since the degree (which is the place that holds the last nonzero coefficient) isn't fixed. So the polynomial $$ 8x^3 + 5x + 7 $$ is "really just" the sequence $$ (7, 5, 0, 8) $$ or, if you like $$ (7, 5, 0, 8, 0, 0, \ldots) $$ where the zeroes go on forever.
What "really just" means there is that if you know the sequences of coefficients for two polynomials you can calculate out the sequence for their sum. Just add the sequences element by element. You can also calculate their product. It's a little harder to write down the algorithm, but you can figure it out if you understand how writing a polynomial the high-school way with powers of $x$ makes the multiplication automatic.
You can even divide one polynomial by another as long as you're willing to allow yourself a remainder (and allow fractions for the coefficients). You may in fact have learned how to do that and called it "synthetic division".
You can also "evaluate" a polynomial at a number $n$ when you know its coefficients.
What all this means in practice is that you don't need "$x$" or its powers to think about polynomials. The "variable" just helps to keep the polynomial arithmetic straight. And that's so useful that we almost always write polynomials with an $x$ rather than as a sequence of coefficients.
Finally, this abstract view lends itself to further abstraction! All you need to know to manipulate polynomials (written as sequences) is how to add and multiply the coefficients. So the coefficients themselves might be polynomials. So, for example, you can think of $$ 4x^2y^3 + 6xy^3 - 2xy^2 $$ as "a polynomial in $x$ whose coefficients are polynomials in $y$": $$ (0, -2y^2 + 6y^3 , 4y^3) = ((0), (0, 0, -2, 6), (0, 0, 0, 4)) $$ or as "a polynomial in $y$ whose coefficients are polynomials in $x$". (You write that one.)
The coefficients can even be matrices, when you learn what matrices are and how to add and multiply them.
Further thoughts:
You can think of the algorithms for addition and multiplication you learned a long time ago as like the arithmetic of polynomials, only more complicated. When you "collect like powers of $x$" in a polynomial, you just add up what you see. When you "collect like powers of $10$" in ordinary arithmetic you have to simplify further by "carrying", so replacing, say, $21 + 7 \times 10$ by $1 + 9 \times 10$.
If you relax the requirement that the coefficients be $0$ from some point on then you are dealing with a (formal) power series, traditionally written $$ a_0 + a_1 x + a_2 x^2 + \cdots = \sum_{n=0}^\infty a_n x^n . $$ You can add these and multiply them with the usual polynomial rules. They are "formal" power series because trying to evaluate them by substituting a value for $x$ is much more subtle than it is for polynomials. You'll study that in calculus. (And formal power series have uses that don't depend on evaluation.)
Then you can decide allow a few terms with negative powers, like $$ 4x^{-3} + 7x^{-1} + \text{ an ordinary formal power series} . $$ These are called "Laurent series"; they come up when you study functions of a complex variable. You have lots of nice mathematics to look forward to.
Note: in this answer I will try to motivate the definition which is used in more advanced contexts such as "abstract algebra". This may go beyond what is in a typical pre-algebra book, but I hope it will show how the mathematics community has found a way to come up with a workable definition, even it is less obvious at first.
It is hard to define polynomials because there is a tension between several of their key properties, which don't quite agree:
A polynomial can be written as an expression in the form $a_0 + a_1x + a_2x^2 + \cdots + a_nx^n$ for some $n \geq 0$ and some choice of coefficients $a_0, \ldots, a_n$.
The sum of two polynomials is a polynomial. The product of two polynomials is a polynomial. Overall, the collection of polynomials is the smallest collection that includes all the numbers, $x$, and is closed under addition and multiplication.
The expressions $(x+1)(x-1)$ and $x^2-1$ determine the same polynomial.
If we want to use something like (1) as a definition, we end up with the issue that $x$ and $2x$ are defined to be polynomials, but $x + 2x$ is a polynomial according to (2) but is not literally in the form shown in (1). So we have to define a "simplification" operation.
If we want to use something like (2) as a definition, then we still have the issue of defining when two polynomials are equal, as (3) points out.
In general, although it is tempting to define polynomials in terms of "expressions", this causes more trouble than it is worth. So it is common in more advanced texts to define polynomials as follows:
A polynomial (over the real numbers) is a sequence of real numbers $(a_i : i \in \mathbb{N})$ in which at most finitely many of the terms are nonzero. Two polynomials are equal when they are the same sequence.
So $(2,1,0,0,\ldots)$ and $(0,1,3,0,0,\ldots)$ are polynomials according to this definition. Of course, the "polynomial" $(2,1,0,0,\ldots)$ is meant to stand for $2 +x$, and $(0,1,3,0,0,\ldots)$ stands for $x + 3x^2$. But in these definitions we do not define the polynomials in terms of the expressions. Rather, we view the expressions as nothing more than notation - shorthand - for the sequences which are actually polynomials.
We continue the definition by defining addition of polynomials using the formula $(a_n) + (b_n) = (a_n + b_n)$.
Multiplication is defined in a way analogous to the Cauchy Product: $(a_n)(b_n)$ is defined to be the sequence $(c_n)$ where $$ c_k = \sum_{i=0}^k a_i b_{k-i}. $$ This is exactly the formula you would discover if you multiply polynomials in the usual, pre-algebra style.
In this way, the collection of polynomials in the variable $x$ is identified with the ring $\mathbb{R}[x]$, which is also defined as the set of finitely-supported sequences of reals with the operations shown above. These definitions of the operations take care of simplification automatically, so we do not need to worry about "unsimplified" polynomials in the formal definition.