How to truly secure a hard-drive?

One word: LUKS

LUKS is a full-disk encryption method. At boot-time, you have to enter a passphrase. With the given passphrase, a key slot is unlocked and the actual key for encrypting the data is retrieved. LUKS can be seen as a encrypted partition which holds another partition.

Because most users have multiple partitions (the / partition and swap), it's often used with LVM to avoid having to enter a password for each LUKS encrypted partition. LVM can be seen as a special partition holding multiple partitions (simplified). The structure would look like this:

Disk
+-LUKS partition
  +-LVM partition
    +-/
    +-/home
    +-swap

Using the alternate CD, you can create a new installation using LVM + LUKS. Within the disk partitioning step, an option is visible for copying data from another partition. If you do not mind reinstalling the whole system, backup your files and settings and do a new installation using the alternate CD.

For a more correct documentation of LUKS (cryptsetup), see Cryptsetup FAQ.

I am aware of two solutions: LUKS and Truecrypt (discontinued).

Truecrypt is generally used for encrypting part of your hard disk or an external disk. It is possible to encrypt entire hard disks with Truecrypt, with a small unencrypted partition for pre-boot authentication and decryption. However, this only works with Windows systems. I would only use Truecrypt for non-bootable disks. Truecrypt's source code is publicly available, it's free of charge and it's reliably cross-platform. It's not included in Ubuntu's repositories because it's not strictly open source.

Update: The TrueCrypt developers have mysteriously discontinued it and now recommend other solutions.

LUKS/cryptsetup is better integrated with Ubuntu, specifically Nautilus and Disk Utility. If you're installing a fresh system, it's very easy to encrypt the entire hard drive using the alternate CD. There's an option in the install process that does it all for you automatically. I would definitely recommend using LUKS unless you have to use Truecrypt.

I'm currently multi-booting an unencrypted Windows system, an unencrypted Debian system and a LUKS encrypted Ubuntu system (which includes both the root partition and swap). Getting this set up was complicated, but there are guides online. One thing to be aware of is that LUKS LVMs cannot be resized to the left, and resizing to the right is complicated.