In photoshop go to MODE first and change to 16 bit. Then rez up. Some people say if you want to double the size, it helps to rez up twice in 50% increments. If you want to sharpen, use Unsharp Mask in 16 bit. When you are finished, go back to mode and change to 8 bit.
There is a program called "Genuine Fractals" which is supposed to do a better job than photoshop, but the 16 bit trick works nearly as well and is a lot less hassle, not to mention the savings of the cost of more software.