Actually the Gates don't talk to each other before they connect, they don't have to. Each gate has 38 reference points programmed into them. To open up a connect you enter the 6 coordinates based off those reference points, which projects the beginnings of a wormhole near the target gate. We can tell this because the gate draws large amounts of power as it is being dialed, not just when the 7th chevron locks. It is mentioned at various times when dialing 8th and 9th chevrons that even the attempt to dial the 8th or 9th chevron would be too expensive unless they were sure it was going to lock.
If there is a functional gate within range it draws that pre-wormhole to it. The exact range of this is unknown, but I assume it is a fairly large distance. Otherwise as the planets and their solar systems move through the galaxy they would leave the target area pretty quickly. This throw/catch mechanism is necessary since even with 38 available points of reference it would be virtually impossible to hit the tiny and (relatively) fast moving target of a stargate across interstellar distances.
This capturing is indicated by the spinning of the receiving gate. This spinning could either be the receiving responding to an attempted connection in it's vicinity, or the receiving gate responding to the power being given it by the sending gate, it is unclear from the shows. I liken it to how a lightning rod "draws" lightning to it, not by acting on the lighting, but providing it the shortest path to "ground". You can also extend this metaphor to explain why a wormhole will jump to a second gate within the target range. If one gate becomes too energy saturated it ceases to be the shortest path to "ground", and the wormhole jumps to the next shortest path, the second wormhole. How stargates determine target precedence is a different question.
If nothing goes wrong by now the 7th chevron on the origin gate locks and all chevrons on the target gate lock. This is where the Kawoosh comes in, when the unstable wormhole interacts with the stargate's disintegration/reintegration. Then the stargates can communicate with each other to negotiate matter transmission, energy transmission, etc.
As long as the reference points in the stargate are fairly up to date, say within 2-3,000 years, all you need to dial is a power source and an address. If you are receiving you don't even need that, leading to the occasional one way trip. However, over time as stellar drift moves both the points of reference and the stargates out of the target area. This is why Abydos was the only gate the Earth gate could reach, in Children of the Gods Carter estimates within a few thousand more years even that address wouldn't work. Once they discovered the Abydos DHD and Daniel showed them the cartouche temple, the SGC had a baseline list of addresses that should work. From there they could determine a way tweak the stargate's reference points to access those worlds recorded by Ra. Later, during The Fifth Race, with the Ancient knowledge in his brain, O'Neill creates a better program to compensate for stellar drift allowing for a more precise reset of the stargate's points of reference.
To counter this the DHD's communicate with each other using the Correlative update system. The DHD's at random intervals, on would assume every few hundred years depending on their planet's relative motion, dial out to other gates they have records of and probably communicate with the DHD on the other side, exchanging data on how the target gate is drifting from the target area compare their update records and update each other with the most recent data. DHD's do store addresses of dialed gates, but not in an easily queryable way. It is how the Adria was able to track SG1 in The Quest, among other times. If the target is shifting then the DHD runs some internal program, then updates the stargate's points of reference.
Because the Earth gate was sealed for so long it was unable to update in this manner. So the DHD could never update the points of reference programmed into the Stargate to account for stellar drift. Each time it missed an update the stargate's points of reference got more and more out of date.
