From what I've heard Gimp is the best free software for doing Minecraft textures being very similar to Photoshop however I have not tried it myself.
I use Paint.Net because I'm used to it and it is adequate enough for the Minecraft skins I make with it but it's not a program I would recommend if you're serious about getting into texturing as it is quite lacking in its versatility.