Skinning your minecraft character is super simple. All you need to do is create a 64px by 32px image and you're good to go!
Ok I'm lying, but its almost that easy. Minecraft will look at the image you create and use certain parts for the separate surfaces of your character. Lets look at how the image is laid out.
As you can see the layout is super simple. Lets also take a look at the basic skin for minecraft.
This skin is blown up five times its original size so you don't have to squint. If we compare the layout with the base skin we can start to get an idea for how many pixels we have for each piece of the skin. The long, slender pieces such as the legs and arms are 4px by 12px, the large squares are 8px by 8px, the smaller are 4px by 4px. With that you should be able to extrapolate the other few odd sized pieces.
Now on to creating the skin. Jump into your favorite editor and create a new image with dimensions of 64px by 32px. With your artist cap on count 8px over from the top left corner, this is where you're going to start drawing the top of your head. Continue on drawing like this using the skin layout image as a reference. Alternatively you can download the minecraft reference skin and modify it.
Once you have a skin drawn up you're going to want to preview it. Notch has made this super easy for us to do. Login to your minecraft account at www.minecraft.net. Now click on preferences. You can see that you can upload your new skin and it will preview it for you. The skin displayed in the preview will be the skin loaded next time you play minecraft. Quick FYI, when in game hit F5. This will toggle third person mode so you can see your sweet new skin!
Please post your skins in the comments. I'd love to see what everyone come up with.
Update 2: It turns out that you can also skin hear gear with the same image. Below is the layout for those of you that also what to include head gear in your new skin.
Now who is going to be the first to create a Darth Vader skin with the helmet?