As everyone has said - start with very simple stuff. Tarballs, file copies etc are a form of Version control, introduce that first as it can be, has been, and in too many cases still is, done that way. Discuss the pros and cons. This will lead to a "tool" to solve the problems
While still focusing on single developer, introduce checkout and commit, compare to / checkout earlier version etc. Don't ask them to set up a repo first... even with GIT of HG, that is too much too soon, as although the mechanics is trivial, the concept is not understood. Get the students use to the idea that a VCS use is normal for a single developer. Repo management, including create, how to backup reliably etc comes next.
Now introduce Merging - hence branching - this is the killer feature of VCS (Except CVS, but this is a uni course in 2012) I would go as far as showing the merge of a complex set of changes by two people (carefully selected to have no merge conflicts). e.g. Looks at this - his 100 lines and your 200 lines in merged into the same file with no typing - Wow. - Then move to showing merge conflicts and discussion on avoidance and then resolution strategies and how to avoid them, when and why (or why not)
Now they have the basic concepts of how 2 people can work together, introduce a "feature branch" concept and a "roll back to fix bug" concept.
Discuss things that cause needless problems with merges, such as white space changes causing conflicts, the cost of layout changes etc tat are not needed. Make a two trival changes to a file, and then merge them. Now make the same two changes and change the formatting of the file in each, (e.g. One change tabs to spaces, the other change indentation from 2 to 4) and ask the students to merge them.
Discuss the distinction between VCS and Configuration Management - many developers have no idea where the line is and think that a good VCS achieves CM. (i.e. VCS stores revisions, CM manages revisions)