Adding boot-level security
Next to the BIOS-level password security, the boot loader is the next level of protection one gets. Linux's popular boot loader, GRUB, provides a built-in feature that prompts you to enter a password before proceeding to boot up the system. Here's a blog entry detailing the simple steps in enabling this security feature. I also recommend that you check out the comments for more tips about the boot loader.
Watch out, though, if you can avoid it, don't password protect your main boot kernel. I had an incident when I had a password protected setup and when the machine rebooted (due to power failure), the system waited for me to enter the password – which was around 14 hours (overnight and then some) – before services resumed.