if they are actually connected over the internet (not through any other way) then it is not surprising really. every client has an IP address that it broadcasts to others as it connects to any other node through a version message. then others send its IP to other nodes and that way it propagates. so your other client eventually finds out about that IP, most likely right away if both are connected to same node(s) and attempts connecting to that IP.