For myself, I use two different programs in combination; Paint Shop Pro and Fractal Design Painter. Paint Shop is great for manipulaing the image in color, size, contrast and gamma, and for joining images together into a form that can be loaded easily. Fractal however carries the lighting, surface and tonal controls I feel are necessary, to give the sprite that full body depth we've all come to expect of game images. I don't know if Adobe Photoshop can make these same adjustments, but if so I'd be a wonderful tool..
Any truly great code should be indisguishable from magic.