I found the tutorial about modeling a shoe in Blender. But the video does not go into one crucial point. It never shows you how to tie the shoe lace. Any ideas?

 Oh well, I think I've managed to work something out.

Not sure how I missed this post. I do not have a clear clue on how to do it but have you looked into Blender Swap website some may have posted a model you can download and perhaps get a feel for what they created I did a quick search and found this being shared on Blender Swap it may give you an idea on how to attempt making it also Blender Swap is free to join and most the models Creative Commons license that descripe usage terms.  http://www.blendswap.com/blends/view/21232

Hope this gives some help

What solution did you come up with?  I looked around for tutorials, but couldn't find anything.  I'm sure curves are involved, but not sure how to tie them.

Here's a tutorial for making a knot that turned up for another software, but maybe it can be translated to Blender too.

http://www.infobarrel.com/How_to_Model_a_Knot_in_3ds_MAX

If you found one like this which is specific to Blender, please let us know.

 "traditionally" I would use curves its fiddly and annoying but gives good results

with blender having the skin modifier now that maybe an easier route if you don't like Bezier curves but not tried it (yet)

 Basically, I just kept rotating the "string" until I had my knot. Took awhile, but I did it.