Well for my version I used the dodge/burn tool but I wouldn't recommend that since it affects the pixels of a layer directly. I would instead make three new layers:
- Mask- this should be a layer to hold a layer mask the same shape as the sprite so you can draw outside the lines and it won't disrupt the background (good for keeping a solid background)
- Highlight (Mode should be "Screen" or similar) to hold white pixels that lighten the underlying layer (like your current characters)
- Shadow (Mode should be "Multiply" or similar) to hold black pixels that darken the underlying layer.
Note that the colors don't necessarily have to be straight black or white, just lighter or darker, and you want to be putting down semi-transparent pixels, probably with like a 7-15% pencil tool.
One other method for adding shading fast in Photoshop is to use Bevel and Emboss under layer effects- but that's really cludgy since it can only follow the outline of a layer, so to use it you'd have to separate everything that overlaps within the sprite into different layers. And even then, it would still look funky.
As for the plank/log problem, BCullis is right, it's all about getting a handle of how to shade basic shapes. Here's a thread of someone having pretty much the same problem: http://www.gamedev.net/topic/633482-why-does-this-look-so-flat/. You should also look up some shading exercises, or even invest in a drawing book since the basics carry over regardless of medium. I have this on my desk right now and I refer to it pretty regularly.
[hr]
For the Head in particular, I don't really remember anything super specific... I made sure that I shaded under his jaw and the left side of his head to his shoulder (the shadow cast by his head on his shoulder). I also highlighted the right side, since that's in my imaginary light source.
[attachment=13057:PlankGuyHead.PNG]
[hr]
Bonus:
I never messed with index color like Dave Troyer was talking about, but here's what it can do:
[attachment=13058:IndexedColor.PNG]
Looks like it makes you collapse your layers, but it will dither for you, which is pretty sweet.
[hr]
As a final note, it doesn't look like your sprites are really pixel art (although that depends on how strict your definition is), since it looks like you're blurring/adding texture without manually manipulating the pixels. That's a whole other topic though.
Edit: Let me know if you have any questions, I should be able to respond tomorrow although anything in depth will have to wait for the weekend...
Good luck!