By default, private messaging is allowed for friends only.
In order to change this to "Everyone" (which I highly suggest you do) follow these steps:
- Go to your settings
- Scroll down to "Allow private messages from"
- Change it from "Friends only" to "Everyone"