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.