Anytime you make a raster image larger you are going to lose quality, it's unavoidable...The program has to "make up" new color information for all the new space. Photoshop happens to be the best program for doing raster images (TIFF, JPG, BMP, etc) IMO, and Illustrator or Freehand are good for vector based drawing.
The nice part about vector is it will scale without any loss in quality because it's a collection of shapes and points, not individual pixels. Downside is 99% of the artwork you get off of the net is raster based.
You have two options here, one menace already mentioned. You can take the raster image, and "trace" it to make it into a vector based picture. This isn't 100% accurate, and it's helpful to have a fast computer with lots of RAM, or a lot of patience as an alternative. Once you are done, you will have a picture that will scale to any size you need and always retain the same quality. This is the most difficult approach, but comes out with the best scaled results.
Your other option is to just rely on the resampling in Photoshop to get the job done. The only thing you can do is choose which image resample you want to attempt. I normally get the best results from Bicubic resampling, but depending on the image, you might want to select Nearest Neighbor. My advice would be to try both and see which gives you the best looking results.