The Avatar is a reincarnation lineage, and hence the new Avatar needs to be located after the death of the incumbent. The time that the Avatar spends between incarnations is usually brief, so an infant born around the death of the Avatar is sought among the people of the next elemental nation in the Avatar cycle.
The cycle is tied to the bending of the ancestors of the Avatar, not the physical place, and so occasionally an Avatar will be born in the "wrong" nation, which has led to delays in locating the Avatar. The avatar-finding methods are not infallible, and sometimes there are long delays in locating the Avatar, as with Avatar Kyoshi. The Avatar Cycle might appear to skip an element if the new Avatar died in infancy or otherwise before being identified, but that has not happened in unquestioned historic memory.
There are many different means for locating and identifying the Avatar. For the last dozen-odd avatars, methods were more or less standardized by each elemental nation, but these are not the only methods that have ever been used, nor are they the only ones that are efficacious.
Earth
The officially prescribed method for locating the Avatar is to conduct directional geomancy in various prescribed sites to triangulate the position of the Avatar. This would be done simultaneously by the Earth Sages according to auspicious astrological circumstances that could be identified across the Earth Kingdom. However, the order of the Earth Sages was disestablished by the Earth King Jialun, and, at least officially, their successors have not attempted to located the Avatar since.
Rituals
The form of the geomantic ritual was codified under the Ri Dynasty, elaborating upon a Hao Dynasty ceremony. After the dynastic transition to the Hao-Ting, the ritual was again modified, and that form maintained thereafter.
In any case, the ritual depends on the intercession of a Spirit and must thus be conducted in a numinous place, typically a mountain grotto sacred to a powerful earth spirit. To increase the accuracy and certainty, and reduce the chances of treachery, the Ri Dynasty conducted it on nine of the so-called Eighteen Holy Mountains, scattered throughout the Kingdom, the subset of mountains being chosen in Ba Sing Se by diviners there. However, since the result of the ritual is a direction, any three mountains will suffice to locate an Avatar anywhere in the world, and though they would ideally be far apart, only the practical limits of precision prevent it from being conducted in three slightly different places on the same numinous site.
In practice, once the approximate location was known by the directional geomancy on the Holy Mountains, Earth Sages traveled there and gathered children born at about the right time in a large circle, repeating the ritual as necessary over several days to find the correct one.
The old form of the ritual is recorded in the State Ritual Practice; the new form that was developed during the Hao Ting is based on the subdivision of land-masses but similarly depends on the involvement of spirits.