The most common method is to extract serial numbers from M/B, HDD and possibly other main system components. As clauslack said, CPU can also be used, but I believe only the second method is actually feasible - I know P-III were the first CPUs to have a serial number, but people weren't delighted with the idea, so very soon MBO/BIOS manufacturers offered an option to disable access to that number, and it's always activated by default. I'm not sure if later Intel CPUs (P4, Core...) have access to the S/N, and I believe AMD never had that "feature".
Also, getting CPUID is not hard. Getting the S/N's of other hardware could be a bit harder though, but I believe at least MBO S/N is provided by ACPI.
Concerning changes in hardware, there are some software systems which are tolerant to some HW changes, an example being the winxp activation. I'm not sure how it is done, but I'd do it by providing several hashes something like:
Hash1 := HashFunc ( MBOSN + HDDSN );
Hash2 := HashFunc ( MBOSN + CPUID );
Hash3 := HashFunc ( HDDSN + CPUID );
In this example we monitor three key components and have the same number of hashes. So you record all three hashes, and if only one of the key components change, at least one hash remains correct. Changing more than one key component invalidates all hashes.
There are likely better algorithms, but I hope illustrates what I meant. Also this can be adjusted to the number of components you wish to allow to get changed.