I found this video on Lifehacker. It’s a time-lapse video of Matt Kohr’s Photoshop drawing tutorial. I’ve never tried digital painting but I have great admiration for people who do it well.
Actually, this is more than just a time-lapse video. It’s narrated and summarizes his earlier tutorials in the series.
The entire set of video tutorials, Digital Painting 101, is found on Matt’s blog, Ctrl+Paint. He posts mainly videos about Photoshop, although he also has some brushes and textures for download.