Does screen sharing work when not on the same local network?

Solution 1:

Yes. And you can make it work through most firewalls if you're both using Messages. Messages will broker the handshake to start the session and then turn it over to the screen sharing app.

Start up Messages and make sure Screen Sharing is enabled:

Find your buddy in your contact list in Messages and click on them. Then select Buddies -> Share My Screen with Buddy... or Buddies -> Ask to Share Buddy's Screen... from the menu bar to initiate a screen share session. You can share control with these sessions.

Solution 2:

Yes, as long as you port forward (vnc://router.address:5900).

VNC default port is 5900, so make sure that your router is correctly port forwarding this. You can change the port in your router settings.

This Apple KB article gives more details about OS X screen sharing.