OK, a bit of a warning. I'm an IT/IS tech, so building secure systems is my day job. This is guranateed to be massive overkill for any application, including mine. If you're serious about making a truly secure (and thus barely usable) machine, this is the way to go.
I have an incredibly crappy laptop that I picked up for literally the price of a new hard disk, and it is 85% done being transformed into as secure a machine as I can make it.
The first step is chosing an operating system. I use linux all day, so I chose Gentoo Linux. OpenBSD would be a great choice too, but for day-to-day use it's significantly slower. Windows is...significantly harder to get a given level of security out of.
The second step was installing and configuring gentoo. I had two options: I could go with uber-scary paranoid NSA Secure Linux patches to make the machine govt-level secure, or regular Gentoo. I chose a vanilla kernel because I was lazy, but when I get bored I'm sure I'll go NSA later. Its a significant pain to set up tho.
Third step was taking care of the swap partition. Linux uses a little chunk of the hard disk to fill in for memory when programs ask for too much. Windows calls this Virtual Memory. The problem is that the swap contains bits of what the memory contains, and it isn't wiped out on power down. This means that somewhere on your swap drive (and probably in your virtual memory file on windows) your password is probably sitting out in plaintext. There are two ways of fixing this: 1) don't have a swap partition. This is easily doable if you have plenty of memory, but its a bit of a pain if you intend to actually
use the machine, or if its very old. 2) Gentoo's Unstable branch has all the scripts built in to transparently encrypt that swap partition. The steps are pretty easy actually.
Fourth step which isn't complete is to set up encryption on the rest of the drive. There are two or three ways to do this. Briefly, you can encrypt the whole dist except for a stub bootloader, as has been mentioned. You can encrypt the entire /home/ directory which has all your users files, or you can have each user's home its own encrypted directory. I haven't yet decided which approach to take. I'll probably do it user-by-user for one reason: I'm the only user on the machine, but having multiple encrypted volumes gives plausible deniability as well as presenting multiple targets to an attacker.
The encryption keys can either be very long passphrases (good) or actual keys stored on a token (USB Key, Better), or both (Best). I'll be using the two-factor auth on this machine.
Again, this is massively overkill, but it cost me no money and it is still a fun project for me. The primary advantage to this is that I don't have to encrypt and decrypt anything; the system does all that for me in the background. As soon as I power off, all the plaintext goes away.
There are more advanced systems that I'm anxiously waiting to become more stable like the humerously-named rubberhose which gives multiple simultaneous encryption levels for the ultimate in plausible deniability.
Anyway, I've ranted enough. I commend you on your paranoia
[Edit: Forgot. One of the most important things is to ensure that no, and I mean NO incoming connections are allowed. Encryption isn't very useful when an attacker owns your OS. Turn off SSHd, samba, xinetd, etc. iptables is easy enough to setup to disallow all incoming connections. Of course no computer is ever truly secure unless it's unplugged, turned off and sealed in concrete, and even then I wouldn't bet on it.]
