One thing I keep asking myself is how does a public address get created?
I know this isn't what the question is getting at, but for a technical explanation of how an address is derived, have a look at Graphical Ethereum Address.
How can you be sure that the address is not already given to another user?
You can't be sure that someone else hasn't already generated a private key that corresponds to that address, no.
When I create an address locally (through geth account new), how can I check if it is synced with the ethereum network?
All addresses exist, it's just that someone must generate a keypair that maps to an address to be able to use it. Once it is used, it appears in the blockchain data, and the network knows that someone has the private key.
When you generate a keypair/address locally, you can check if the address has been used already by checking the address on a block explorer. If it has, you can (obviously) infer that someone has already previously generated a private key that corresponds to the address.
What you can't tell is whether someone has already generated the private key to your new address, but not used it. They may have the same private key as you sitting on their machine waiting to be used. You can't know that.
Also worth noting is that more than one private key can map to the same address. However, even given this, the chances of collisions - two people generating private keys that map to the same address - is very, very small.
Of interest would be:
