There is no best program for spriting. Microsoft Paint works perfectly well. I have a friend who's incredibly talented, and he uses Graphics Gale. Like any tool in the world, it doesn't matter what program you use. All that matters is your level of skill.
In addition, just because Notch uses a specific program doesn't mean it beats everything else on the market.