With the limitations of the HTTP protocol, it's not possible to do this in real-time. That is, you can't do Instant Messages over HTTP. It's just not possible.
The best you can do are private messages like the kind you can send on this very message board (you can do this by clicking on the little "PM" button at the bottom of someone's post). The way this is done is by creating a new table for messages. You'll need at least four columns: sender, recipient, timestamp, and message. When user A sends a message to user B, you simply insert a new row with user A's id in the sender field and user B's id in the recipient field, with the appropriate timestamp and the message in the message field. Now when user B logs in or visits a page, you can make your PHP script check to see if there are any messages in the messages table that have his id in the recipient field.
As you can see, this isn't real-time. The user is only notified of new messages when he visits a new page or reloads the current one. You can sort of fake real-time by using a META refresh to automatically check every 30 seconds or so, but it's still not real-time.
If you're looking for a prebuilt script that'll do this, I recommend a Google search for "php messaging"