You make a "new skin" by changing all entries in the .skin file from "Luke" (if it's the Luke model) to "your skin's name here" depending on what you decide to name your skin. Any time you see "Luke" listed in the pk3, change it to "your skin's name here" (except textures, unless you changed them in the .skin file as well). I'm sure the tutorials above will help you out more than I can.
If what you mean by "NEW skins" is actually "NEW textures", than I suggest you hunt down a copy of photoshop and a good tutorial. Or, you can download GIMP for free. I'm sure there are good GIMP tutorials here and there as well.