I agree with Sion. I know some of my colleagues depends entirely on Photoshop's default Bicubic resampling algorithm to interpolate images intend for large prints on a plotter and I look at the end product, it is pretty good, very acceptable in my opinion.
If you want something more sophisticated, other than Genuine Fractals that Sion have mentioned, Fred Miranda sells a PS plug-in called SI Pro I think. The idea is something similar to Stair Interpolation which can be done w/o any plug-ins in photoshop, go google it. Another app that I've seen in action before is S-spline but it wasn't intuitive to use.