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”.
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).