Well, it's a deterministic wallet. There is a function f which for every n∈ℕ returns the nth address that will be produced.
An address is basically a hash of a public key (we can neglect the rest it's comprised of but it's deterministic as well).
You can get a public key from a private key deterministically.
Every 256 bit number is a private key.
So your wallet just needs to make 256 bit numbers deterministically and do calculations to get to addresses deterministically.
This can easily be done by picking a hash function which outputs 256 bit – let's choose sha256 – and a salt λ. A salt is just something that's added to the input of a hash function.
If your wallet knows λ, it can generate a practically arbitrary amount of bitcoin addresses.
g(n) for every n∈ℕ can be defined as g(n) := sha256sum(λ.n) where . is the concatenation operator. g(n) is the nth private key.
If you use a Linux computer, just open the terminal and type in:
echo "aR3Ba9raAi1" | sha256sum
echo "aR3Ba9raAi2" | sha256sum
echo "aR3Ba9raAi3" | sha256sum
echo "aR3Ba9raAi4" | sha256sum
echo "aR3Ba9raAi5" | sha256sum
echo "aR3Ba9raAi6" | sha256sum
.
.
.
aR3Ba9raAi is λ. The last digit of the parameter echo gets is n but of course it can be more than 1 digit.
Via the output you get:
g(1) = 49fc13b53bf8cbc8607c121066a974f5c803aee04629e11696946f93b16825a6
g(2) = 9462e18f435684eb8bf5008f8e7c717729fbfa505554ef4b3325a3eccc807519
g(3) = d7bde9e8c19959b0abaa5c476a3fc7a4eacf713fe78c9e2a66ac202419ddbf6f
g(4) = d08ddf753bb37b853407f1451334bb042d93ee2179c01244a019229a32fe9c03
g(5) = 4291513728b1a0d96b72df35bafa1f78db1ceaf135d874a3d8e5353aa9408893
g(6) = e04aba61558daaa532d252397e5d5467c8dd64552f987e54245ab759dd0517cb
.
.
.
Those would be the private keys. They are the same on every machine as long as λ stays the same. No between your machines is necessary after they all know λ. g(n) is deterministic and so is everything else afterwards on the way of generating an address. So f(n) can be calculated from g(n).
Of course that's only an example to show you the basic principle behind deterministic address generation. It's strongly simplified and major steps for generating addresses are omitted. This answer should only show you that something can be calculated the same way on different machines without the need of them being able to communicate with each other.
This is also great because everything you need to recover an HD wallet is a seed. You don't need the entire history of what's been generated from the seed because it can be generated the exact same way again.
