Just like Michael H said: “Check the Anyone can register box in the Administration > Settings > General screen.” Check the box next to “Anyone can register” and then click the “Save Changes” button at the bottom.
To TEST this, you have to be logged out. So, if you’re using Firefox for all your admin work, open an Explorer (or Netscape, Opera, Safari, etc., anything BUT Firefox) browser and go to the site. It should show you as not being logged in, and you can test it there because it should have a link to login, and that should have a link to register.
Remember, the setting must be turned on to work, & you have to be logged out to see the link.
Switching between browsers makes it easy to find these things. And, it makes it easy to see the differences in how the browsers (& your customers) will see things.