I was actually pleasantly surprised this past year when dd's kindergarten teacher sent home a rotating kit with practice puzzles for tying your shoes. You got to keep the kit for one night - brought it back the next day - and had an opportunity to tie for the teacher. If you succeeded, you got your name on the wall of fame.

This approach might be stressful for some kids (it was stressful for this mom) - but my dd found it very motivating. She really wanted her name on that wall so she learned how to do it in one night.

If the teacher hadn't sent the kit home, I probably wouldn't have even thought about tying shoes (we are a velcro/slip-on kind of family).