When making a large print (large = 13"x19" or larger) @ 300DPI the program has to "resample" the image to create the required additional pixels. From what I've read the best way to do this is to not do a single 1-pass up-res, but instead to do several smaller, incremental upsize resamples, where each upsize is about 10% larger than the previous one. This is what leads to the name "Stair Interpolation."
I've used Fred Miranda's SI Pro Photoshop add-on to do this and it works well. But perhaps there are even better ways to do it.