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:
apt-get install cryptsetup hashalot
cryptsetup --verbose --verify-passphrase luksFormat /dev/sdb1
cryptsetup luksOpen /dev/sdb1 funnydiskname
mkfs.ext4 -O extents,uninit_bg,dir_index /dev/mapper/funnydiskname
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.