How do I enable private messages for normal users, and not just administrators? Only Administrators can see the "Messages" link when logged in. Non-administrator users cannot. What can I do to alleviate this? 

I've tested by looking at the site when logged in as Bobby, who is normally non-administrator user. No "Messages" link. However, if Bobby is ticked off as an administrator and I log back in as Bobby, I can see the "Messages" link between "My Account" and "Log out" in the upper right corner of the screen. I even get a notification that I have "1 new message".

I've looked through the Private Messages module configuration and can't seem to find setting that corresponds to what I'm experiencing.

I'm using Drupal 7.22 and Privatemsg 7.x-1.4.

The Private Message module is enabled, and all users have a tick in their "Enable private messages " setting.
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.