Hi there,
A few steps I have been using recently to achieve something which I have been reasonably happy with, which is really easy to achieve with limited amount of 'colouring' or science, but quite a lot of time, and heavily borrowing from David's original art.
STEP 1, OUTLINE:
STEP 2, COLOUR:
STEP 3, TEXTURE:
STEP 4, ALL TOGETHER:
Basic process is to have the outline on the background layer, have the colour on a multiply layer above the outline, and have the texture on an 'overlay' layer on the topmost. All the textures are selected from various contiguous areas from David's original art (and some of my stuff as well).
This is as per the Paint.net terminology.
From there I would work on an extra detail layer, add some specular highlights by hand (maybe a low opacity layer, drawing with white) and some shadows to 'finish it off', but you can get to this stage fairly quickly. Also, once the layers have all been flattened and you are happy with the sprite generally, you might want to do some touching up on a pixel by pixel basis.
I'm sure there are a bunch of other ways, but hope this helps?