It basically depends on how tight you want to couple your software to the underlying hardware. For example you could get some hardware information from the registry, read out the MAC address from the LAN card, retrieve the gfx manufacturer, the CPU id, etc. and hash all these data.
You could then use this hash as a challenge code which is sent to your company. The customer then receives the signed (with your private key) version of this hash.
Upon start up your application is able to check if the signature of the hash is good or bad (i.e. has been signed by your company).
This not only binds your software to a certain hardware configuration, but also forces the crackers to patch your application (because they would need to patch the public key from your executable and replace it in order to write a keygen). Many people consider twice installing a crack obtained from various sources in contrast to just entering a valid serial copied from a keygen.
Edit:
In order to check the signature of the hash, anything from RSA over DSA to ECC can be used. I can recommend Crypto++ or libTomCrypt for that.