Let $x_1 < x_2 < \ldots < x_n$ and $y_1 < y_2 < \ldots < y_n$ be two sequences of $n$ real numbers. It is well known that there are polynomials that "interpolate" in that $f(x_i)=y_i$ for all $i$, and the Lagrange interpolating polynomial even warrants a solution of degree $ < n$. Now, what happens if we want the polynomial $f$ to be nondecreasing on the interval $[x_0,x_n]$ ? Is there always a solution, and is there a bound on the degree also ?
4 Answers
This problem has appeared before in literature and is now well understood, I guess. The general version is when you have no restriction on the $y_i$'s and you ask for an interpolating polynomial that is monotone on each subinterval $[x_ix_{i+1}]$. The first paper proving the existence of such a polynomial is:
W.Wolibner, "Sur un polynom d'interpolation", Colloq. Math (2) 1951, 136137
but it is a nonconstructive proof, as it uses the Weierstrass approximation theorem much like the answer given by Harald HancheOlsen above. Another proof for the case $0=y_0\le \cdots \le y_n=1$ is given in "Polynomial Approximations to Finitely Oscillating Functions" by W.J. Kammerer (Theorem 4.1) and the nonconstructive aspect of his proof is the use of uniform convergence of appropriate Bernstein polynomials. In "Piecewise monotone polynomial interpolation", S.W. Young proves the same theorem and makes the final remark that the existence of such monotone interpolating polynomial is in fact equivalent to the Weierstrass theorem. On the other hand Rubinstein has some papers devoted to proving the existence of interpolating polynomials which are increasing in all of $\mathbb R$.
The first paper which gives bounds on the degrees is, I think,
E. Passow, L. Raymon, "The degree of piecewise monotone interpolation", which is here
and an improvement is made in "Exact estimates for monotone interpolation" by G.L. Iliev. Note that the bounds are in terms of $$A=\max \Delta y_i=\max (y_{i}y_{i1}) \qquad B=\min \Delta y_i \qquad C=\min \Delta x _i$$
And no uniform bound exists.
To add to Gjergji Zaimi's informative answer: It is easy to see that the degree cannot be bounded in terms of $n$ alone, even when $n=3$.
Suppose that we want $f$ of degree $m$ such that $f(0)=0$, $f(1)=\epsilon$, and $f(2)=1$, and $f$ is increasing on $[0,1]$, where $\epsilon>0$ is small. Then $f(k/m) \le \epsilon$ for $k=0,\ldots,m$, so the Lagrange interpolation formula shows that for fixed $m$, the coefficients of $f$ are $O(\epsilon)$, so $f(2)$ is $O(\epsilon)$ and cannot be $1$ if $\epsilon$ is small enough. In other words, the degree of any solution $f$ must grow as $\epsilon$ shrinks.

2$\begingroup$ Nice argument. So this brings up the question about sparse interpolation  in which the number of nonzero terms is bounded. $\endgroup$ Commented Mar 1, 2010 at 7:29
I don't know if this has been studied, but at least if you forget about a bound on the degree, a sledgehammer approach gives you a positive answer. For simplicity, assume $x_i\in[0,1]$ and proceed by induction on $n$, with the induction hypothesis being the existence of an increasing interpolating polynomial $p_n$. To get from $n1$ to $n$, let $$p_n(x)=p_{n1}(x)+(xx_1)\cdots(xx_{n1})q_n(x)$$ where $q_n$ is a polynynomial to be determined. Given $p_{n1}'(x)>\epsilon>0$ we have a little wiggle room: We merely need $q_n(x)$ and $q_n'(x)$ to be very small for $0<x<x_{n1}$ (exactly how small left as an exercise) and $q_n'(x)>0$ for $x_{n1}<x<1$. To achieve this, write $$q_n(x)=\int_0^x r_n(x)$$ and use the Weierstrass approximation theorem to let $r_n$ approximate a suitable continuous function. Adjust with a positive multiplicative constant to hit $p_n(x_n)=y_n$ exactly.
The astute reader will notice a problem with this: If $p_{n1}(x_n)\ge y_n$ this prescription loses. So we have to make sure that $r_{n1}$, after shooting up to a nice big value around $x_{n1}$, comes quickly back down to a small value in order to have this not happen. This complicates the proof quite a bit though, and I am not about to work through the details. I'd be interested to hear about pointers to the literature.
I just came across the paper by Powers and Reznick "Polynomials that are Positive on an interval" http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.9773&rep=rep1&type=pdf
In particular they point to a theorem of Schmudgen who gives a characterization of polynomials positive on a specific compact set.