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.
Genuine Fractals and S-Spline are pretty good programs...
A trick when upsizing in Photoshop is to increase the image size by 10% each time, till you reach your desired size... seems to give better results than if you increase one shot... and if you have Photoshop CS and above, try using the bicubic smoother option rather than the just bicubic or bicubic sharper... for resizing large amounts, you could try mixing 4 bicubic smoothers with one bicubic sharper... you would need to do a final sharpening of your image after you reach the required size... donno if it works for others but seems to work for me
As for downsizing, if you need to do that like for output to web, resize directly to required size using bicubic sharper...gives you better image quality overall...
Basic interpolation works by fitting certain polynomials over the original image and then evaluating the intermediate points using the polynomials. higher order polynomial leads to sharper image but with halo/ringing/peaking effects. bicubic is higher order than bilinear interpolate. this two methods are very "ancient"
There is an advance method called SuperResolution.