If you share all your playlists, this new playlist will just appear on the computer of the person that's connected to your computer. If you choose which playlists to share, create this new one, with your message, and then choose it as a playlist to share. If the other person is paying attention to when the playlists change, or notices that a new playlist has become available, then they will see the message.
For instance, I was connected via Rendezvous and someone was viewing my playlists. I made a new one that said "I'm on ichat/Rendezvous" and that person saw it like two minutes later, because then he got on Chat via Rendezvous, and said "saw the message, neat trick!"
[robg adds: Yes, I know this is a simple hint, and that if you've got users on Rendezvous, you could just message them in iChat instead.]

