How do I encypt Time Machine with Mac OS X Lion?
Time Machine does have a checkbox to encrypt the backup, but it will read, encrypt, and write every block of the disk - which can take a long time. If you are using a new drive it is much faster to encrypt it with Disk Utility first.

The encryption is handled by the OS – not Time Machine. Lion will prompt for the password whenever the disk is attached. Once the password has been entered it looks like any other disk to Time Machine.

n.b. you will not be able to use an encrypted disk with older versions of OS X.