What is the OEM Product key stored in?

On PCs made my Dell, HP, Lenovo etc. You often get a OEM Key, Which allows you to install windows on that particular PC, If you attempt to install windows with that key onto a different PC, it'll not activate. So What is this key stored/registered on? The Motherboard? CPU? Or how does microsoft know that that key belongs to that PC? And if so, If I replace those parts will the key not work?

It is typically the configuration of the MOBO and the CPU.
I have never tried to replace a CPU like that so I wouldn't know whether that would be an issue or not. But I do know that if you replace the MOBO, then it would be considered a different computer and there "may" be an issue there. Often you can call Microsoft and tell them your issue and they will issue you a new product code if they agree that you still have it installed on only one computer.
The product key information is stored in the registry.

I'll use windows as an example.

when you install windows with a Product key. That key is registered with Microsoft when you connect to the internet to activate windows.

Microsoft make a note of the setup, motherboard/CPU etc that the Product Key is registered with is kept on a database.

when you reuse the key on a different machine, they know it's a different machine because of the different motherboard, so the key will not be valid.

Microsoft have also introduced periodical checks with some windows updates. So the key is checked at random times to make sure it's genuine.

There are two kinds of licenses (product keys):

1) OEM
2) retail

Microsoft knows the difference because they are the ones who issue them.

OEM licenses are system builder licenses that are issued to computer manufacturers (DELL, HP, etc) from Microsoft. Microsoft's terms for the license grant that builder the rights to install and activate Windows on each computer they build. In such, they are like a mini-Microsoft (for the lack of a better description) in that the computer manufacturer is responsible for Windows on that computer (which is why you call the computer manufacturer when your new computer's Windows has issues, and not Microsoft). The computer manufacturer license is only for the computer they install Windows on at their factory. Microsoft does not grant them any ability whatsoever to transfer that license to a 2nd computer. This is why an OEM license is tied directly to one computer, and one computer only, and can never, ever, be transferred to a 2nd computer.

The product key is stored in Windows on the hard drive.

During the activation process, the product key + hardware ID (which comes from Display Adapter,
SCSI Adapter, IDE Adapter, NIC MAC Address, RAM Amount Range, Processor Type, Processor Serial Number, Hard Drive Device, Hard Drive Volume Serial Number (VSN), CD-ROM / CD-RW / DVD-ROM) and this combination of information is stored on Microsoft's activation server.

The retail license doesn't have the same restrictions. When you buy a retail copy of Windows, you can transfer that Windows license to another computer BUT ONLY IF YOU CALL MICROSOFT. You can't just arbitrarily install it on a 2nd computer without their intervention. Retail Windows is still a one-computer license, just like with OEM, but the difference is that OEM has no transfer rights but retail does have transfer rights (but again, only with Microsoft intervention… Microsoft has to delete the registration information off their server and transfer it to the new computer, is why)

Forget it! It's a code flashed onto the bios by windows good luck cloning a bios chip.