How to draw stickmen. No, really, how?
Are there any good tutorials on this?
First of all create a story board with all characters and list all the elements you will be using, such as backgrounds and objects. Next is to look up your favorite illustrator and use that as a simple guide. Like Scott said the artist is you. If you draw a body it tends to be 6 to 7 1/2 heads high.. Make a cross, draw a circle on top and have a line come off it, upside down v for legs. Once that's accomplished then make the lines to rectangles and section off so it looks like clothes. Use pencil lightly, outline with a fine to medium point sharpie and use Crayola or similar colored pencils to color them. Yes, you have Bob Ross for painting, I learned from Mark Kistler shows. Shading, marker everything, though my style comes from someone I worked for. Get inspired from other artists.
Draw on paper or draw in photoshop and print?
If paper, which type of pen to use?
They look like they used index cards. If you aren't using the originals to shoot the video then use a grainy recycled paper. Try not to use expensive coated or laser printer paper, you can avoid glare that way, whether you shoot or scan. Plus coated is really slick and prone to smudges.
What to watch out for when drawing?
Draw what you see. Everything is a shape. Think about when you leave someone a message. You write the word "call", it doesn't look like "F-R-H-2". The video, and I'm serious, is what got me into pencil and ink and after watching a few you'll realized he's the Bob Ross to cartoons. Hope this helps.