You can resize an image through resampling. Some computer programs, like Powerpoint do this automatically, without you even noticing. When an image is resampled, the computer uses interpolation to create a brand new set of pixels with smoother edge transitions and smoother transitions through color and density gradients. You can actually get pretty nice results from some resampled images. The computer might not be able to reproduce blades of grass that were not captured in the original image, but it can reproduce the smooth curve of a hillside, or the round shape of the eye's iris.
In Photoshop, click image:resize:image size: and make sure that you have checked bicubic resampling and maintain proportions. The results can actually be very good. It is better not to make a single gigantic leap throught resampling, from 640x480 to 6400x4800, for example. Increase in steps equivalent to about 40% increase at a time until you get to the final image size you would like.