Thus created he them, each in the image of Steve

Skinning your Minecraft avatar, is really quite easy, the best way which I found does not involve downloading an editor at all even. MCSkinner is browser based and starts you off with the default Steve skin. Once you finish your pixel art, it links you directly to the uplaod page where you can log in and update your avatar.
You can download your existing skin here :

The default skin is good place to start, but sometimes being begat by Steve is not a good place to start of personalizing your online character's appearance if you really want to be set appart from the crowd. Skins are simply .png format graphics as show above, and you can download one from a nubmer of different sites. The end result:
Not too shabby.
  1. MCSkinner and other editors all allow you to start from a skin you have snagged elsewhere on the web. 
  2. So download a skin to your computer, and then load it up in the skin editor you have chosen.
  3. Save the skin as a file on disk, and then login to minecraft net to update with your new file.
  4. Fire up your Mminecraft client to see the fruits of your labour.