First of all, as far as i know, and have been told, the lineart, or the outline, is just as important, if not more important then the shading, you can't get something to look good if the lineart is just bad.
I've made some tutorials for shading. i'm not sure if they're that good, but i think they cover some of the basics, and some techniques you can apply.
I will also pm you a link to a pixelart site, and directly to a page with al sorts of tutorials.
programs to use:
I prefer MSpaint myself, as it is simple to use, and has no auto AA(anti-aliasing), but there are all sorts of programs to use, and you could probably google stuff like gimp, paint.net, photoshop, stuff like that, everything is suitable.
I hope i haven't been saying too basic stuff for you, and that most of this is useful.