If I'm sitting down to play a game, one thing I don't want to do is read instructions. Console games don't even come with printed manuals anymore, and users are going to expect a much bigger time investment than with a web game probably.
What I do want to do is: play the game. I would recommend against a video for new users - you're asking them to make a time commitment before they know if they are going to like the game or not. An overlay is better, but it's still something that people have to pay attention to. It's real easy to just glance at some text, click away, and then be confused about how the game works.
The best tutorials are the ones that are integrated into the gameplay in some way. Some way to slowly explain the mechanics to players as they are playing an introductory level. The goal should be to make players go through the tutorial without them ever knowing it's actually a tutorial.
Ghost Trick (iOS) is a reasonable example of walking the player through the first level of the game, although one that's way too long (disclaimer: I wrote the linked article).
Quento (also iOS) is a game where you swipe to solve math problems. It introduces the player to the game's mechanic right on the title screen, making the player swipe "quento" to start the game. It's a great way to start a game.