This page will link to a variety of tutorial videos.
David Sparks has released his much anticipated Keyboard Maestro Field Guide with over four hours of video separated into 76 videos in 8 sections covering a broad range of Keyboard Maestro facilities, full of “heaps of dangerous knowledge, tricks, and hacks to make your Mac dance”.
Easy, Powerful Mac Automation for Creative Pros using Keyboard Maestro. 15 lessons over an hour and a half.
Macs Productivity Keyboard Maestro for Beginners video series covering starting with Keyboard Maestro, text expansion, triggers and actions, groups and palettes, and variables and tokens.
Paul Minors has done a very nice overview video of getting started with Keyboard Maestro.
my apfelworld has an extensive YouTube and Twitter presence covering Keyboard Maestro and other automation topics (it is often in German, but there is so many good ideas it is worth looking at even if that presents a language barrier).