How do you protect your software from illegal distribution?

There are many, many, many protections available. The key is:

• Assessing your target audience, and what they're willing to put up with
• Understanding your audience's desire to play with no pay
• Assessing the amount someone is willing to put forth to break your protection
• Applying just enough protection to prevent most people from avoiding payment, while not annoying those that use your software.

Nothing is unbreakable, so it's more important to gauge these things and pick a good protection than to simply slap on the best (worst) protection you are able to afford.

• Simple registration codes (verified online once).
• Simple registration with revokable keys, verified online frequently.
• Encrypted key holds portion of program algorithm (can't just skip over the check - it has to be run for the program to work)
• Hardware key (public/private key cryptography)
• Hardware key (includes portion of program algorithm that runs on the key)
• Web service runs critical code (hackers never get to see it)

And variations of the above.

Whatever route you go, charge a fair price, make it easy to activate, give free minor updates and never deactivate their software. If you treat your users with respect they'll reward you for it. Still, no matter what you do some people are going to end up pirating it.

Don't.

Pirates will pirate. No matter what solution you come up with, it can and will be cracked.

On the other hand, your actual, paying customers are the ones who are being inconvenienced by the crap.