Host Discovery
Manual discovery, client A knowns who client B is
Discovery through broadcast UDP which is used by lot of games for LAN play. A client sends out a packet to the broadcast address for their subnet. The peers can choose to pick up this broadcast and respond. The downside is that this is limited to the current subnet. The more general INADDR_BROADCAST (255.255.255.255) works for all subnets on the local-link, but it cannot be routed, so won't work over internet (this is what DHCP auto-configuration uses).
Discovery through a central (Rendezvous) server. Each individual client knows the address of the server, and the latter informs them about each other. This technique is used by IRC, Voip, IMs and by most 'peer-to-peer' networks.
Communication
After the initial discovery is done you want to be able to talk to eachother. On the internet this can get tricky. Most people nowadays have their own router and sit behind a NAT, so direct connections are impossible.
Using a Rendezvous server, you can possibly talk to each other using the server itself. client A tells the server what to say, and it in turn tells client B, since both clients have an outbound connection to the server.
It is possible for the clients to talk to each other without the server proxying. This requires either DMZ, port forwarding or UPnP. DMZ will basically forward all incoming connections on all the ports to a given local IP. Port forwarding only forwards certain ports to local IPs. UPnP is a bit more advanced, the client requests that the router temporarily forwards a port to it, and you tell the other client via the rendezvous server where to connect.
Chatting app implementation
The easiest solution to your problem is most likely to use a central server, which is known by all the clients, that proxies host discovery and possibly the communication between the clients. If you want the clients to communicate directly, you can just proxy host discovery, and then let either DMz, manual port forwarding or UPnP do the rest.
Another solution would be to just have direct communication through NAT traversal techniques discussed above, and do manual host discovery.
Yet another solution would be to use a public webserver and 'abuse' its ability to insert content to chat with each other.