There are many modules out there to prevent spam registrations in Drupal, but many of them involve some sort of Captcha, which I hate, or a paid for service. Stopping fake site registrations should not make it harder for the legitimate people trying to register on your site, and having to pay to prevent spam does not sit well with me.
While Drupal does have a setting to "Require email validation", I do usually have this enabled, but it does not stop the actual registration process and your user table will increase in size pretty quickly, also, some bots seems to be able to get around this too.
Here is a list of the modules I enabled to stop spam registrations to great effect.

Include a honeypot field

The honeypot module is a great module to implement as your first line of defense. It adds a hidden field to your forms, that when a value is added, the form will not submit.
It also has a "Honeypot time limit" setting that is the "Minimum time required before form should be considered entered by a human instead of a bot.". Not though, that using this setting will disable page cache for whatever page that the form on, As on many of my sites have the registration form on all/most pages I usually set this to 0 effectively disabling it so the pages still cache.

Block certain username or email patterns

Often spam registrations have email addresses at a few common domains and you can stop this by enabling the user restrictions module, but this may not be enough and maybe you want to check the username field for a pattern instead. Enter the Regex Registration Deny module, This is a module that I created as I wanted a little more control than the alternative modules provided. It allows you to check the username or email address for specific patterns using regular expressions. As an example, I was getting many spam registrations with a username with many numerals at the end, with this module I was able to easily deny any registration when the username ended with more than 2 numerals.

Verify the email address exists

See update at end of article
Some spam will not get caught by the above methods, particularly when the registration email address is from some randomized domain, enter the Email Verify module. Reading the description of the module, it seems that it was created to just check if the person registering entered their email address correctly, but it also goes a long way to stopping spam registrations.
The module "tries to solve this problem by checking that the address really exists when it is entered by the user. First, it checks if the domain/host part exists at all, and reports an error if it does not. I found that this step alone catches between 1/2 and 2/3 of typos. Second, it tries to validate the user name too, by sending a HELO/MAIL FROM/RCPT TO chain of commands to the SMTP servers for the found host."

Using the above methods, I have brought spam registrations on my sites to almost 0.

UPDATE: The email verify module can seem to get your IP blacklisted as outlined in the issue HERE