You do not need Truecrypt or to encrypt the partition.
Encrypting the partition after removing it will simply supply a powerful overwrite. It works beautifully, but not because it's encrypting: just because encrypting a new, empty partition is, at most, exactly the same thing as overwriting the old one with random data.
On modern hardware, forensic techniques are not capable of recovering overwritten information economically. It is possible, but the cost is staggering.
Recovery is based on detecting redundant and residual information, but both types of information inevitably decrease when information density and I/O rate go up. Nowadays, both media density and speed are such that redundancy and residual are minimal, which means that recovering lost information requires technology, skill and time. All three are expensive (a magnetic scanning microscope capable of appreciating hysteresis residue at the single bit level is still priced at around one million USD).
So, overwriting is enough.
And if you really feel paranoid, you can overwrite the same information again (and again).
Suppose you want to make /dev/sda (the whole disk) unreadable. Just boot from an external medium (e.g. a Linux live distro) and run one of the following commands
dd if=/dev/zero of=/dev/sda bs=1G count=1 # Faster but incomplete
dd if=/dev/zero of=/dev/sda # Faster
dd if=/dev/urandom of=/dev/sda # Possibly more accurate
Zeroing the disk up to the first gigabyte kills the partition table and likely all metadata for the first partition. It is possible and reasonably affordable to recover most of the data on the first partition (past the first gigabyte); it is possible and easy enough, even for unskilled personnel, to recover the whole data for any further partition after the first one (sda2, sda3, ...). You can zero the first gigabyte of each partition first (use of=/dev/sdaX), then the disk, if you want to quickly trash all partitions.
Zeroing the whole disk makes the data utterly unrecoverable for wannabes, skilled people and recovery specialists. It is still maybe possible to recover something using ruinously expensive equipment. If you have a zeroed disk, do not send it to data recovery professionals as you would just waste money; but a black government lab with million-dollar equipment might be able to pick up the stray magnetism from the platters, and recover information from that. They would also probably have the budget for rubber-hosing the same information out of you.
Overwriting the disk with random information makes the data twice as hard to recover. See above. It also takes several hours for a large disk.
You can also, on some disks, trigger the SECURE ERASE procedure, which is like the above but done in hardware and somewhat faster. You can use hdparm for that using the --security-erase-enhanced flag if the HDD supports it.
A faster and more secure alternative (not always allowed)
I have now for three times "erased" the HDDs in laptops I had to give back by purchasing brand new HDDs from a local retail shop and swapping them. A 1TB 2.5" HDD costed about €80 one year ago. It saved me all worries of "data recovery" - you can't recover something that's never been there - and it took less than ten minutes to perform the swap. Plus, I have a full backup of all I had on those laptops, since I kept the old disks.
Given that I would have been charged more than €80 to perform a reliable secure erase on a laptop (I myself would charge you more than that), I feel I ended up ahead.
Of course, you need to be allowed to tamper with the laptop at the "screwdriver" level.
In the future
There are some disks that implement hardware based disk encryption. What does this mean? It means that upon disk initialization, in the factory, a unique code is generated and stored into permanent rewritable memory in the hard disk. From then on, all data sent to the hard disk will be encrypted using that code before being written on the magnetic platters, and will be decrypted upon reading.
From the user's point of view, nothing is different from normal. You could (actually you usually need to) encrypt again the data if you want to have it protected by Bitlocker or Truecrypt or the like. Since encryption speed is way faster than host data transfer rate, no difference in disk speed will be detected.
Except that now - if a command is sent to the hard disk to forget the encryption key and generate another - the whole content of the disk can be lost forever in a few milliseconds. Unfortunately, on these devices, if the controller board containing the key is damaged, the data is also instantly made unrecoverable (controller failures are usually recovered by replacing the controller with a compatible one. Here, the new controller would have no way of knowing the encryption key, and would thus be able to access the drive physically, but not to decrypt it correctly).
(This kind of firmware usually allows for the key to either be transparently used, as above, or specified or be further protected by a BIOS supplied key at boot time through a specific protocol called OPAL).
So, if you can get a laptop with OPAL/HDE capabilities, secure disk erasure would be a matter of a couple of minutes.
