Most DNS servers have a mechanism that allows the DHCP server to make dynamic updates to the local (internal) zone. If you have this feature at your disposal, then you can just use DNS names, and let the systems guys make sure that the DNS records are up-to-date with the DHCP leases.
A similar DNS-based approach could be accomplished on the wider internet using a DDNS service like dyndns.
If you can't use DNS, then you're stuck with a UDP broadcast-based approach. This is the same mechanism that protocols like DHCP, bonjour, and SMB use to find other computers on the local network without knowing their addresses; and this approach will only work in the same contexts where those technologies work (typically, only within the local network, and definitely not across the greater internet).
In java, you would accomplish UDP broadcast messaging via the DatagramSocket class.
Quoting the api docs:
UDP broadcasts sends are always enabled on a DatagramSocket. In order to receive broadcast packets a DatagramSocket should be bound to the wildcard address. In some implementations, broadcast packets may also be received when a DatagramSocket is bound to a more specific address.
Example:
DatagramSocket s = new DatagramSocket(null);
s.bind(new InetSocketAddress(8888));
Which is equivalent to:
DatagramSocket s = new DatagramSocket(8888);
Both cases will create a DatagramSocket able to receive broadcasts on UDP port 8888.\
If your two machines are located at disparate locations on the internet, and you can't use a DDNS service (like dyndns, mentioned above), then your best bet is to build a central registration server. This would be a simple server (could even be a web service) that runs at a known address on the internet. Each of your client machines would register with the central registration server, thus the central registration server would know the IP addresses of both machines. Then each machine could request the other's address via the central registration server. You'd have to put some thought into to security in order to protect against malicious "poisoning" of your registry, but otherwise, this would be fairly straight forward.
EDIT:
I just discovered JXTA. It's a set of tools for building java applications with peer-to-peer networking features. I don't have any direct experience with it, but it looks like it would accomplish what you're looking for (and probably save you a lot of work over having to build it all from scratch).
In fact, it looks like the subproject p2psockets does exactly what you want.