How to encrypt external devices using a cross-platform solution?

You could also consider installing Truecrypt on your USB. Once installed, use TrueCrypt to create an encrypted container, which can be opened with the software on the key. Saves you time installing software on multiple computers, still leaving you with the encryption you wanted.

Update since 2014, from TrueCrypt site:

WARNING: Using TrueCrypt is not secure as it may contain unfixed security issues

This page exists only to help migrate existing data encrypted by TrueCrypt.
The development of TrueCrypt was ended in 5/2014 after Microsoft terminated support of Windows XP.

I would use EncFS which is available for Linux, OS X and Windows. Advantage is that you can also use it with cloud storage since EncFS encrypts on filesystem level and therefore the changes only affect the files changed not a partition as a whole.

On Linux it's as easy as

encfs ~/Dropbox/encrypted ~/Private

I presume it's similar on Windows but I have only tested it between OSX and Linux so far. You can find a little more info here

On Linux Gnome Encfs Manager is a pretty handy GUI tool to manage EncFS encrypted directories, store passwords in keyring, etc.

sudo add-apt-repository ppa:gencfsm && sudo apt-get update && sudo apt-get -y install gnome-encfs-manager

Truecrypt is probably your best choice, though you'll need to be able to install the software on any computer you want to use.

Update since 2014, from TrueCrypt site:

WARNING: Using TrueCrypt is not secure as it may contain unfixed security issues

This page exists only to help migrate existing data encrypted by TrueCrypt.
The development of TrueCrypt was ended in 5/2014 after Microsoft terminated support of Windows XP.

There is DoxBox:

Open-Source disk encryption for Windows

• Easy to use, with a 'wizard' for creating new 'DoxBoxes'.
  
• Full transparent encryption, DoxBoxes appear as removable disks in Windows Explorer.
  
• Explorer mode lets you access DoxBoxes when you don't have admin permissions.
  
• Compatible with Linux encryption, Cryptoloop "losetup", dm-crypt, and LUKS. Linux shell scripts support deniable encryption on Linux.
  
• Supports smartcards and security tokens.
• Encrypted DoxBoxes can be a file, a partition, or a whole disk.
• Opens legacy volumes created with FreeOTFE
• Runs on Windows Vista onwards (see note below for 64 bit versions).
• Supports numerous hash (including SHA-512, RIPEMD-320, Tiger) and encryption algorithms (Including AES, Twofish, and Serpent) in several modes (CBC, LRW, and XTS), giving more options than any other disk encryption software.
• Optional 'key files' let you use a thumb-drive as a key.
• Portable mode doesn't need to be installed and leaves little trace on 3rd party PCs (administrator rights needed).
• Deniable encryption protects you from 'rubber hose cryptography'.

After open-source computer program FreeOTFE for on-the-fly disk encryption (OTFE) got discontinued, the DoxBox fork sprung up.

This means that you can encrypt a partition using LUKS (How to encrypt external devices?), and then access it from a Windows machine using DoxBox.