Just the same as you would on a desktop. Laptops aren't unique beyond being portable. They have normal hardrivs and OS installation just like their big brothers. So just pop in your installation CD and go!

Just for clarity though -- When you say adding a Linux partition, do you mean just an OS install, or are you trying to set up a dual-boot Windows/Linux machine?