How do I enable private messages for normal users, and not just administrators?
You need to set up permissions to use Privatemsg.

Go to example.org/admin/people/permissions (Home > Administration > People, Permissions tab) and check privatmsg boxes for Authenticated User role.

It might be also convenient to create "Messenger" role with these permissions, and grant it to all users by default. That way, you will be able to ban someone from messaging by simply taking role away from him.