If you are not connected on the same LAN segment (both computers on the same network) and you are going through a router, chances are the router's firewall is blocking the connection.
What you have to do is open/forward the ports on the router Apple screenshare (remote desktop) uses to communicate. The ports are:
TCP: 5900, 5988
UDP: 5900, 3283
Screen sharing behind a firewall-- What ports?
One thing that I personally like to do is test out on the same LAN segment first (behind the router firewall). This way I know that my machine is fully functioning and the service is working properly. This way, when trying to troubleshoot a connection issue across the router, the changes of it being my machine is greatly reduced.
You will need to edit your REMOTE router to allow incoming connections of the ports that I mentioned. You do this by:
1) Find out what IP address the computer is using
2) Go into the router admin page via web browser (it will the the "router" address in your network settings. You will need the username and password.
3) Under Firewall, you may see an option to forward different ports. Create entries for the ports listed above. In each entry you should have a "source" and a "destination." In source, leave blank for "all" and for destination, enter the IP address you got in step one. This will forward all traffic from these ports to the computer.
4) You should now connect over the internet.
If that doesn't work, I suggest looking into TeamViewer. It's a third party solution, you will need the software on both machines and it is a bit slower. However it is much easier than configuring a router.