As with any other network service, Screen Sharing has a set of virtual “ports” which isolate network traffic for that protocol since it and web traffic and other network services are all using the same IP address and connections. These ports must be opened in all network devices for all computers involved in the screen sharing sessions. This means firewalls on the local computer, as well as any routers or hardware firewalls must also be set up to pass traffic on the following ports:
TCP: 5900 – 5902, (3389 for connecting to Windows machines)
UDP: 4500 (for Back to My Mac users)
Depending on the network devices used, these ports can either be opened completely, or forwarded to the local IP address for the desired computer, but you will have to consult the documentation for your router to see about how to change these ports. Additionally, if your router supports “UPNP” (Universal Plug & Play) or “NAT-PMP” (NAT Port Mapping Protocol), then it should work for Back to My Mac. The list of routers in this Apple Knowledgebase article are some that support Back to My Mac and other screen sharing.
I really need to get around to making the firewall behave for screen sharing.