If you want to send a message you'll need to set up port forwarding on any device that acts as a server (any device which creates a socket server). Port forwarding is done on the Router. The reason you cannot connect to the other client is because they are hidden behind their routers firewall. Their address to the rest of the world is actually the address of the router, not of their physical computer. On their local network they have a different address then what the rest of the world sees, and the router figures out what messages from the outside world need to be sent to the client based on an address translation table.
Given your architecture, this would mean that all clients need to have their routers doing port forwarding, which is of course unfeasible (imagine gtalk or aim requiring users to do port forwarding).
The more common architecture is to have the Server do the work of rebroadcasting messages to the connected clients and maintain tables to lookup whose talking with who. This way there is a single server which will need a static ip (or be port forwarded), and all users are simply clients which connect to the server socket and read messages from it.
For actual code describing the second architecture please see http://pirate.shu.edu/~wachsmut/Teaching/CSAS2214/Virtual/Lectures/chat-client-server.html. Then the machine which is running the server code either needs a static ip or if it is behind a router needs traffic from the port it is listening on to be forwarded.
So on the server code you will bind to the ip assigned from your router (something like 192.168.1.2 at some port say 5000). Then go to your routers configuration page (it may be 192.168.1.1 see http://www.wikihow.com/Port-Forward/Open-Ports-on-a-Linksys-Router), and forward port 5000 to the address 192.168.1.2.