As suggested by
This tutorial says Paint Shop Pro because that is the program I use, but this tutorial can be applied to any graphics program, be it MS Paint or Photoshop
This is how I do shading in pixel art. It's really simple when you get right down to it.
EDIT: Interested in dithering and further methods on how to accomplish it? Check out my new tutorial