As of right now, besides a better graphics editor than MS Paint, you also need the terrain editor. This is because the skins ain't separate files but are bound up in the terrain files. So you use the terrain editor to export the skin, then you use the graphics program to paint it how you want it, then you use the editor again to import the skin back into a terrain file. And this means that new skins won't work on existing maps--they only work on maps you make yourself.
The above system looks like it's in for a change in AH2, however. The ability to use multiple skins online and offline seems to imply that skin files will be separate entities in AH2, so you won't need the editor to get to them. Also, it looks like new skins will work with existing maps.
