vimtutor - Just run this on the command line and it will open up VIM's built-in tutorial (which of course, is just a text file that contains instructions to edit itself).
Interactive Tutorial - Covers the basics and lets you try them out as you go.
Learn vim For the Last Time: A Tutorial and Primer - Much longer tutorial that's quite complicated but has a lot of good stuff if you're curious.
Vim Adventures - Game version to learn the basic movement commands, but the full game costs $ and isn't worth it.