This works in 11.04, 11.10 and 12.04 - however, the fix for 12.04 isn't in the main repositories yet, it should be there by the end of May however.
The "Share Desktop" feature of Empathy uses vino as a VNC server and vinagre as a VNC client by default. The feature also seems to be supported only with Jabber/XMPP protocol. I tested this on Ubuntu 12.04.1 (updated on October 2012) both 32 and 64 bit. "Share Desktop" works after installing the vinagre package (vino was there by default) and using a Jabber account.
You typically do not need to set up the share desktop feature before you use it. All you need is to make sure that the person on the other end is using Empathy an has "vinagre-preferences" running. Simply right click on the person's name and select "Share My Desktop..."

You'll get this message while the other person gets a prompt.

The other person will see something like this:

When you're done there will be a final message to make sure the person is disconnected:

If the menu entry is grayed out it means that either the other person doesn't have support for it or you might be using a protocol that doesn't support the feature.