This is a very basic feature of any social networking site, but still I am not able to find it on Google+.
I have tried messaging many Google+ users who are in my circle and also have me in their circle, but didn't find any link/button even remotely saying "Message".
Can someone help me out here?
P.S: Sending e-mail through gmail is not a substitute to sending private message in Google+
Best Answer
Private messaging in Google+ is handled the same as all other messages are - it is intentionally very consistent.
To send a private message, use the "Share what's new" box to write the message. In the "Add more people" section, remove any other people or circles (including "Public") and start entering the name of the person you want to message. You should be able to auto-complete them. You can also plus-mention them in the message, and this will do the same thing.
You can then "Send" as normal. The message will appear in their stream and they will get a notification if they have that configured.
Additionally, if you look on a person's profile, there may be a small envelope icon directly to the left of their profile photo, above the banner image. This will do the same thing. Not everyone has this enabled, however. To enable it, edit your profile and select "Change contact settings", and make sure that "Allow people to send you a message from a link on your profile" is checked (and either public or visible to the circles you want to use it).