I've recently assembled a pretty comprehensive tutorial on how to make your own textures, starting with little to no knowledge of what to do and (hopefully) providing enough to get you up to at least a working ability. Be warned, the following are text and image heavy (links are in the "Part #," if you can't find them):

Part 1: This covers how to extract files from Minecraft, and which files you should actually be able to edit.

Part 2: This covers some of the basics of using GIMP, a freeware - open-source image editing program. This is pretty important if you've never edited any images with any software before.

Part 3: And this covers the basics of actually making a texture, how to make it map in one or two directions, and a blurb about how you'd reprocess the files into Minecraft again.

I hope to expand on the tutorial as time allows, including how specifically skins and objects work (the above processes work on skins and objects, but skins and objects are set up differently and are easier to work on if the difference is understood), how to compress and distribute your work, and maybe someday some more advanced GIMP tutorials and color/image theory stuff.

For now, I'm working on a secret project, which will be posted to the same blog, and tutorials on some buildings I've developed and think are cool.

I'll try to answer any questions and comments.