From the very start, get them used to the command line.
How to use commands such as ls, mv (to move a file as well as to rename a file), clear, ls, su and other such common commands. Teach them now to use man and info pages to get information on how to use commands, and give them excersizes that requie the use of command options to get particular output. Teach them how to use su and sudo to get root authority to accomplish tasks.
PATH: what the PATH variable and how to set the value. How to issue commands by using the full path to the executable from anywhere, and how to cd to a directory to give the command from within that directory. (two somewhat different meanings for path).
Teach them about software repositories and tools to get software: apt-get (aptitude, synaptic), yum, yast, wget, ftp, etc.
Archiving files using tar. Installing software using .tar archives, rpm and Debian tools to install software.
Bootloaders: lilo and grub: what they do; how to configure them; how to add another OS to the system and add it to the bootloader.
Partitioning and OS installation.
Using liveCDs to try out distros before installing (perhaps have an .iso on file that they can burn to cd). Show them distrowatch.com as a resource for more distros.
How to set up and boot an .iso on the hard drive (without cd/dvd drive). How to mount an .iso to see the files within and add/subtract files.
Teach the difference between /etc/bashrc and ~/.bashrc, and how to customize the shell prompt.
Command line text editing using sed, vim, emacs.
Gui text exiting using kate, joe, gedit, nedit, or other such editors.
Introductory shell scripting to automate common tasks.
Perhaps a bit of awk and python.
Hardware configuration with whatever tools are in the distro you use to teach the class.
Introduce them to www.google.com/linux
as a resource for finding answers to questions they may have.
Equally important, introduce them to www.linuxquestions.org/questions
Those are the things that come most readily to my mind. Surely I've left out equally important topics. No doubt others will fill in the blanks I've left behind.