When creating an animated sprite, do you move from finished frame to finished frame, or do you start rough and add details later?

Start rough, definitely! Draw a stickman the size of your sprite and animate that first. Then, when you're happy with the stickman movement you can begin adding a solid colour on top of each stickman frame to sketch out the outline for your sprite.

The sprite you have is a good start but the gun is kinda hanging I think, like its melting or something.

Fixed the chin a little and colored the mouth brighter. For feminine looks, you'll want to cut back on sharp details and try to make things round and err.. mellow   On a small sprite like this I might even consider dropping the mouth altogether, especially for the femmes.



EDIT: Or just listen to NaCl, hehe 

Like Anarkhya said, you can shave down your palette quite a bit. For this kind of sprite, four or five colours should be enough for each colour ramp. Also, try to define shape by putting your highlights and shadows in the right places. Unless your character has a spotlight pointed right at him he most likely is illuminated from above. I did a quick edit of his pants (bottom pic) to illustrate and bumped the colours down to 32 while I was at it:

Yello,

that's a nice piece so far but it has some depth-consistency problems. The pants are really nice shaded with highlights on the left leg and the right leg mostly in shadows, but the shading on the jacket doesn't fit with it at all. Right now the jacket part looks flat, like a stone-relief, it needs lots more shadow on its right half to follow the leg shading. Not too eager about the leather-cracks either, they should have much less contrast to avoid the rock-like feel. Remove the highlights on the cracks and/or use colours closer to each other. Maybe even remove the cracks altogether, you can still convey a sense of leather with some regular wrinkles with strong highlights.

Hope that helps