You can send a UDP broadcast. This sends out a UDP message to all computers on a subnet. Typically, it goes like this:
1) The server is listening on a UDP port.
2) The client sends out UDP broadcast and then waits X seconds for a response.
3) The server responds to the UDP message with another UDP message.
4) If the client gets a UDP message within the timeout, it assumes it came from a server. The message received has the IP of the server, and the client can try to connect via TCP, etc.
A couple notes:
* The broadcast will be blocked by most network hardware. It is really only useful for discovering servers running on the LAN.
* UDP messages can get lost, so the client might want to send a few broadcasts.
* You can see the UDP broadcast code for the client side here:http://code.google.com/p/kryonet/source/browse/trunk/kryonet/src/com/esotericsoftware/kryonet/Client.java#408
* You can simplify your life by requiring the user to input an IP for the client to connect to. Find the IP address of the server (eg by going to it and typing "ipconfig") and use that for the client.
* For running a server visible to the internet, you can use a service like DynDNS to give your server a name instead of needing to remember the IP. You'll need to configure any routers that your server is behind. Setup the router so that communication on the ports your server uses goes to your server machine.