First of all, just because you're not pming doesn't mean you're not interacting. Obviously, pms are good places to grow relationships.
Let me give you a little story. I used to be a very addicted involved member in a certain online game. For that game, there was what's known as a fansite - what Sitepoint is to the web, this forum was to that game. A forum and also a help guide for anything in-game. One thing that I really liked was having 'community events' where we would all get togetheringame and hang out and play. Now, can you imagine Sitepoint members getting together and building a website? No, not really (although I think that that would be really cool hint, hint...), but when you do things as an entire community then that really helps people to grow together and enhance the community and not individual relationships.
If you aren't in any rush, I find an effective way is to hint to someone else that you sent them a pm. W/ your moderating staff (if you have them), tell them to do that. That is try something like:
It's really subtle, and a lot like advertising. Next time, someone might remember that and shoot the other person a pm. That helps people know that it's possible to pm other users.
As for how to? Meh. Most people know how to email, and I don't think that PM is much different than email, if maybe a bit less formal (I'm like a suit-and-tie guy in email )