I had to fight with this recently to screen share with my mother so hopefully I can shed some light on some issues you may be having.
Per Apples support page on Screen Sharing:
You can share screens using AIM, Jabber, Google Talk, and Bonjour. You can’t share screens using iMessage or Yahoo!.
That being said, you'll want to go to the preferences pane of iMessages and make sure you have an account added and enabled that supports one of those protocols. In my case, I added my Google Talk account. The other person will ALSO need to have one of these accounts enabled and signed in. I would presume on the same service also.
Back on the main iMessage window, you'll want to make sure you're signed into that account by looking at the bottom left hand corner of the window and making sure you're online.
Once that's done, you'll want to switch to the user you would like to screen share with and click on the details link in the top right. Then select the icon with the two overlapped screens, like below, and select the appropriate option.
The person on the receiving end of your screen share request should be able to accept it and that's that.
I do remember there being some weirdness around some security issues with Google Talk so you may have to do some research about that if it doesn't work, but that's the general procedure I had to follow for it to work.