When I told you that this was not possible, I was wrong.
My understanding is that you have points $(x_1, y_1), (x_2, y_2), ..., (x_n, y_n)$ through which you construct an interpolating function $f$. Now you need to add another point $(x_0, y_0)$, and construct a new interpolating function $f^*$ for which it is true that $f^*(x) = f(x)$ for all $x \in [x_1, x_n]$. I thought it was not possible to keep the function value unchanged in the interval $[x_1, x_n]$ when using higher value interpolation, but this is not the case. See below:
Let's make an interpolation function from cosine values between 0.1 and 1.0:
ifun = Interpolation@Table[{x, Cos[x]}, {x, .1, 1, .1}]
It looks like this:

The trick is that when we add an extra point at $x=0$, we need to keep all derivatives unchanged in $x = 0.1$ up to the order of interpolation.
You can get the order of interpolation like this:
ifun["InterpolationOrder"]
(* ==> 3 *)
Let's get the derivative values in the first point:
derivs = Table[
Derivative[i][ifun][ifun["Grid"][[1, 1]]],
{i, 0, First@ifun["InterpolationOrder"] - 1}]
(* ==> {0.995004, -0.0995897, -1.00396} *)
And inject them back into the function, while adding a new value $f(0) = 2$:
ifun2 = Interpolation@Join[
{{{0}, 2},
{ifun["Grid"][[1]], Sequence @@ derivs}},
Rest@Thread[{ifun["Grid"], ifun["ValuesOnGrid"]}]
]
Notice that the function is unchanged for all values greater than 0.1:
Plot[{ifun2[x], ifun[x]}, {x, 0, 1}, PlotRange -> All]

If you are wondering where I got this special API to InterpolatingFunction where we do things like ifun["Grid"]: I simply looked into the DifferentialEquations`InterpolatingFunctionAnatomy` package that the other answers used.
InterpolatingFunctionmakes this technically possible. If you are willing to accept a different type of Mathematica object (notInterpolatingFunction), then it is definitely possible. – Szabolcs Jan 28 '12 at 20:19Interpolation[{{{0.1}, 0.11, 0.73, 0.92}, {{0.3}, 0.91}, {{0.4}, 0.95}, {{0.6}, 0.49, 0.87}, {{0.9}, 0.95, 0.25}}]... – J. M.♦ Jan 28 '12 at 23:51