If you already have the image in PSP then woodchip is right. If you are able to scan the image in, then scan at the highest true dpi (not interpolated - this just causes artifacts). At the end of the day, the dots (pixels / inch dermine how large and image you can produce without pixellation). Unless of course you have some way of converting your image into a Vector format. In which case your image data is stored as mathematical representation and, in theory, is capable of infinite enlargement.
The best way to do this with a jpg in Paint Shop Pro is as follows:
Open the image, click Image on the top tool bar, and select resize. Choose the size you want, select either the hight or width. (Make sure that maintain aspect ratio is ticked). Select the resolution you want, and then select Bicubic Resample.
As has been stated, you will not get perfect results, but you will avoid pixel blockiness. You can improve the results somewhat by using Effects, sharpen, unsharp mask.