Found this very nice howto, which I almost followed to the letter, except I did it in Ubuntu and currently more stuff is working out of the box, so you don't need to do all the steps.

I'm working on an USB stick which is /dev/sdb1 in my system.

Steps I did take:

1. apt-get install cryptsetup hashalot
2. cryptsetup --verbose --verify-passphrase luksFormat /dev/sdb1
3. cryptsetup luksOpen /dev/sdb1 funnydiskname
4. mkfs.ext4 -O extents,uninit_bg,dir_index /dev/mapper/funnydiskname
5. cryptsetup luksClose /dev/mapper/funnydiskname

Now pull out your disk and re-insert. If everything went well, your GNOME, XFCE, KDE env should now popup an 'This disk is encrypted, please enter the passphrase' question.