A prime case study of your question would be when the Tollan moved to Tollana. They built their own Stargate with the help of the Nox because the planet didn't have one (SG-1 Season 3's Pretense), and thus no gate had an address for it. You could also use the Earth gate(s) since they were out of the network for quite a while.
Short Answer: Based on evidence from the episodes, when a new gate goes online either:
- The creator manually puts in a few addresses and dials them, or waits for the gate to use a subspace transmitter to transmit at lightspeed to the nearest Stargate that is part of the network, then that dials back. At some point in the future, a correlative update happens, creating a "phone tree" that registers your gate with all active gates, but presumably this registering happens on a smaller scale whenever a gate gets dialed. Thus any gates you dial register your gate location as active, and then any gates dialed by them also register your gate as active, thus any of them can dial your gate address in return.
- A Stargate can always connect to any gate, so long as the Stargate knows what glyph goes to what point in space. Thus a Stargate never needs to inform any other Stargate about its status (except Destiny for the sake of convenience).
(Very) Long Answer: SG-1's Season 7 episode Avenger 2.0 establishes that gates need to periodically dial each other to account for stellar drift.
We know that the 'gate network has to undergo periodic correlative updates in order to compensate for stellar drift. Now, we've never witnessed it, but we believe that the 'gates dial each other automatically to transmit the new coordinates that apply to each address."
Later in the episode, Baal exploits this (with the help of the Avenger virus) to bring down the gate network, but the SGC can still dial out because they have a McGuyvered DHD system that didn't get the updates. Given these two things, it seems that outgoing Stargates need to know some information about the address it's pointing to, but an incoming Stargate doesn't care. So a new Stargate would only need to know the address of Stargates it is connecting to, but the receiving Stargate wouldn't, at least until they want to dial it back. (In other words, Stargates only know a handful of the 2 billion or so potential addresses). In other words, they need to "register" certain gate addresses as valid addresses.
It's worth reiterating that which Stargate is on the receiving end of a location doesn't matter because the Stargate it dials into can be switched at will (e.g. SG-1 Season 5's 48 Hours). There doesn't seem to be a need for a Stargate on the receiving end to broadcast it's position. Heck, in SGA Season 5's Enemy at the Gate, the Wraith Hive Ship from the Pegasus Galaxy was dialed by Atlantis, even though it had never been to Earth. So Stargates are definitely location-based, not gate-based.
However, Carter said in Avenger 2.0 that the correlative updates are supposed to happen every few hundred years and that they'd never seen one before, so the Tollan in our case study couldn't have triggered the correlative updates in order to get their gate on the network. This is supported by the fact that the planet Euronda was able to call Earth (SG-1 Season 4's The Other Side), despite the fact that the Earth gate would have been buried for years and thus would not have been part of the most recent correlative update.
One way this could be avoided is by the transmitters mentioned in the SGU Season 2 episode Common Descent, where Eli says the following:
Gates use short-range sub-space transmitters. It's how they communicate status updates with Destiny before it even drops out or dials.
Some methods of faster than light transmission are near instantaneous (e.g. the Replicator collective, the Tok'ra ship tracking network seen in SG-1 Season 8's Reckoning Part 1), but it seems pretty clear that these transmitters don't use them because it would defeat the reason of having to dial other Stargates in order to do a correlative update.
If such a sub-space transmitter is used, it would need to work by transmitting to the nearest Stargate at lightspeed or slower. Once received, that Stargate could fire off a correlative update via gate dialing to all known Stargates (being near instantaneous and updating the whole galaxy in a few hours), which would instantaneously update Stargates in a matter of hours. A lightspeed transmitter could take several years to get to the next Stargate (the nearest system to Earth, Alpha Centauri, is 4.37 lightyears from Earth), but the fact that we didn't see Tollana until a season and a half after the Tollan moved there does leave this possibility, although SG-1 would somehow have had to miss the correlative update for Carter's comment that they'd never seen it to be true.
A far more efficient way to do this would be for the Tollan to manually put in a few addresses they knew, like Earth, and then they could dial them instantly. We know that addresses can be manually modified, since Atlantis is the only one that can dial or be dialed from Earth, as noted in SGA Season 1's Before I Sleep (especially since Janus was able to quickly made it so that only Earth could dial Atlantis). It's worth noting that the Antarctica gate was up at the time that this happened, but Atlantis has always been dialed by the Giza gate. The Antarctica gate would have been registered with Atlantis (and presumably it would not have passed on the info to other gates in a correlative update), so the only reason we could contact Atlantis was because we hardcoded the address into our custom DHD rig.
A reasonable failsafe for the Ancients would be that any address dialed out could be dialed back. This would require a transfer of gate addresses whenever a gate is dialed. Basically it's just a correlative update, but only between two gates, so it's done on a much smaller scale and done much more efficiently (no wasted power from gates dialing too often).
So a new gate would just have to hardcode one address and then dial it. Any gates dialed from either of those two would then have the address. This would also mean that you could never get stranded. If you build a Stargate on A and hardcode B's address, you could then dial B, which would remember A, then dial C which would remember A and B, then go back to A. Pretty soon, it'll be at a point where you can get dropped off on a random planet by a ship and still directly dial home, because there's some chain of Stargate dials connecting that planet and your original planet. A correlative update every few hundred years ensures that all gates, including those not used for the last few hundred years, are registered with each other. I'm guessing that this was done more frequently when the Ancients were building gates, but now since gates aren't moved often, the correlative update only happens every few hundred years.
It's possible that a subspace transmitter is used in tandem with this "gate address forwarding" mechanism: the Stargate transmits to the nearest Stargate that it is active, and perhaps any gate addresses it knows is active, and then eventually it will reach a Stargate that someone is using, at which point it can be instantaneously transferred to another Stargate, possibly in a distant part of the galaxy. It'd take a lot longer, but it would ensure that a gate dropped on a new planet would be able to be connected to as soon as it lets another gate know that it's online.
This still creates a problem with intergalaxy connections (e.g. Earth to Atlantis, Icarus Base to Destiny) especially give the relative distance, but note that this only occurs in places important to the Ancients, like Earth and Atlantis, or somewhere manually dialed by the SGC. It's possible that the Stargates automatically calculate stellar drift between these important locations. The fact that Destiny has Earth stored in its computer, and can connect to it based on the address pulled from it, supports this. Of course, since Destiny moves so much, it has a unique dialing sequence so it can be called no matter where it is. Possibly Icarus Base's gate manually registered Destiny, but it may not have been necessary. O'Neill with the ancient database in his head probably just manually registered the Asgard planet on the fly, although apparently it's not that hard to manually register a gate on the SGC DHD rig (again, the Giza gate wasn't active when Janus made Atlantis only dialable from Earth, so it wouldn't have been registered on the Giza until we manually did it).
So to throw all this together into how the SGC Stargate got on the network:
- The Giza gate gets unburied
- We can contact Abydos because it's the closest gate. Had stellar drift happened, we'd have to wait years until the subspace transmitter sent a message to Abydos and it dialed back with some active coordinates, or the next correlative update happened
- Abydos can dial back because it knows the Earth gate is online
- Either gate's subspace transmitter tells another gate that Earth is active and eventually someone dials Chulak thus registering Earth with it, or Apophis on a whim decides to manually register Earth's address to see if it works
- We figure out the stellar drift problem and start manually registering gates, although sometimes that's unnecessary
- SG teams start gallivanting around the galaxy and at each Stargate they dial, that Stargate gets registered with Earth
- Other people use the Stargate on a planet that an SG team has visited, thus registering Earth's Stargate with planets they have never been to. (E.g. Chulak has Earth registered, which dials the Stargate Apophis uses on his ship during his invasion of Earth, which last correlative update had registered the Alpha Site planet Daniel goes to)
- Either someone dials Euronda from a planet that has Earth registered or a subspace transmitter reaches Euronda saying that Earth is online.
- A correlative update happens in Avenger 2.0 which synchronizes every planet, thus every Stargate has Earth registered
The Atlantis gate would either be on the receiving end of correlative updates, but never the transmitting end, or it went to Athos, Athos got registered with Atlantis (which it wasn't previously registered for because Janus made it so that only Earth can dial it) and then when Athos dialed Atlantis back, it got all of the gate addresses from Athos' trading partners and all the other gate updates about any gates that the Wraith had moved. Destiny probably works the same way, except it relies on subspace transmitters of nearby gates (and most likely has a special way of tracking Earth, it's point of origin, since it actually was in the database).
EDIT: To make this theory even longer, it would be possible that any gate that goes online would instantly be able to dial any gate, thus there is no need for "registering gates" or even any sort of meaningful "gate network." The whole point of the correlative update is to just update what point in space is referenced by which glyph. This is supported by the dialogue in Avenger 2.0 where it is said that the virus "is like swapping the keys on a keyboard". To continue the analogy, this means that over time the y would change from the "th" sound of thorn to the modern letter with the key staying the same. So if you were to map out which glyphs go to which points in space, you could use this new method.
The issue with this is what happens when the gate network goes down as happens in that episode. I'd like to think that since the Ancients had so many failsafes with the Stargate that the gates would correct such a problem if it ever occurred, which would be possible with aforementioned methods.
Of course if this is the case, it's not clear why you would have gate addresses change as part of stellar drift. It's possible that normal DHDs would have sort of a "forwarding address" system for planets that get remapped as part of a correlative update. This would mean you wouldn't wake up one day after a correlative update and discover that the address home no longer works because it's been switched to a new address. As long as there is no ambiguity between two gate locations, it'd make sense that a DHD would accept either the familiar gate address or the actual gate address. The SGC DHD rig obviously didn't have this, so they had to manually account for stellar drift.
So that's my grand analysis. If it's too complex or there are any inconsistencies, I'd blame it on the fact that I'm piecing together at least four different ways that Stargates work written by a number of different writers from three different series who were more interested in making an interesting script for one episode than planning out the full mechanics of the Stargate network!
