The usual way is to have some fault-tolerant server where services register and can then look for other services - Curator framework implements that over zookeeper.
If you want autodiscovery then you should probably implement some sort of gossip protocol so that the servers would know which other servers are out there in a reliable way. You should keep in mind that getting gossip protocols right is tricky (e.g. some of past Amazon cloud failures where due to problems in their implementation)