to send a Private Message, you use the little tab below a profile pic that says : Send Message. it has the choices that people want it to have.

some say all these: Send Public Message (that means post on the profile page);

Send Private Message (the receiver get a little notification like you did, and no one but they can read it);

and Send Email (it will go to the email they registered at PC with, and your email address that you gave PC will be used to send it).

you might have noticed that you had options on who to let send you messages when you set up your profile page. you can change your own under "Customize Profile" > Edit Options > Messaging and Notifications (about halfway down the page)...