Generally, if we have n+1 data points, there is exactly one polynomial of degree at most n going through all the data points. What can we tell about existence of polynomial of degree n+1? How can we find polynomial of degree n+1 for a table:
x: 0 1 2 3
y: 1 0 -5 -20
Suppose you have a set of points $\{(x_1,y_1,\ldots,(x_{n+1},y_{n+1})\}$. Construct a polynomial $p_n(x)$ of degree $n$ going through the points. Then you can find a polynomial of any degree $n+k$ going through that set of points. You could, as Arturo points out, add any $k$ points, distinct from your original set, to the set of points then find a polynomial of degree $p_{n+k}(x)$ going through those points using your method of choice. Then you have a polynomial of degree $n+k$ going through your original points.
If $k$ is particularly large, you could do this with the method above coupled with multiplying $p_n(x)$ by a polynomial which interpolates the points $\{(x_1,1),\ldots,(x_n,1)\}$ (so that it increments the degree but does not change the value of $p_n(x)$ at your $x_i$'s).
As another method, you find a polynomial of degree $k$, say $g(x)$, and then form $$ \tilde{p}(x)= p_n(x) + g(x) \prod_i (x-x_i) $$ so that $\tilde{p}(x)$ takes the values $y_i$ at each $x_i$ but is of degree $\deg p_n(x) + \deg g(x)= n+k$