Note: I am using Paint Shop Pro 9, i'm not sure if this can be converted to any other version. You don't need PSP or Photoshop to pixel, MS Paint works fine. I just find it much easier to do it in PSP or PS. Keep in mind there are other ways to pixel, this is just how I do it.
First start out with a pixel base. When pixeling I highly suggest you zoom in to about 600% or whatever works for you. [Example]
Once your done drawing out your base, you have to fill in everything. It's better to use colors that look good together, and only 2 or 3 base colors. [Example]
Now you have to shade everything, you can't really be 'taught' how to shade, it is just like trial & error do it untill it looks good. [Example]
This is what it looks like with shading.