I use GIMP. Usually I start by drawing the sprite outline with the solid edge pencil tool in a single color, or maybe a few colors if I know some parts should have different colors. Then I use the paintbrush tool for texturing (except very sharp features). I usually use lighten/darken only, or similar modes are useful to stay within the shape (but of course there are other ways to do that). With the different brush types and opacities, you can quickly create many kinds of textures with this. Finally I do shading by choosing very dark/light colors for the brush, usually a very low opacity and the darken/lighten only modes. Sometimes I use layers when complex shapes overlay (like leaves and snow on trees).
At least that's what I feel is a good method when I have time (I have also made pixelated crabs and stuff in Paint).