#Dwarves marry outside their clans
Your question seems to stem from a misreading of this phrase:
marriage is a sacred rite among the dwarves, taken very seriously because it requires two children to move away from their homes to start a new family in the clan
You seem to have read this as "two dwarves from the same clan move away to marry, therefore they are all related to eachother", but that's not what that phrase means. It's not implying that dwarves only marry within their clan, else there'd be no reason for anybody to move away in the first place. Their "home" in this sense is the dwarven hold, not the house they live in inside that hold.
It is a sacred rite because two children need to move away from their respective holds to get married, which is a very big deal for dwarves, who consider moving away from their home a terrible thing.
They then start a new family, within the clan.
The family is what you'd consider a normal human family, the parents and the kids. The clan is their extended family, through marriage or blood. But to Dwarves, that clan is just as important as their own children, hence 'extended family'.
Your confusion also seems to stem from the fact that dwarves do not have surnames in the traditional sense. Thorin Stoneshaft is "Thorin of the Stoneshaft Clan", it is not his surname. If he marries, and the new family decides to live with the Goldhammers (and their respective elders agree to adopt him into their clan), he is now Thorin of the Goldhammers Clan, or 'Thorin Goldhammer' for humans who don't understand clans. It isn't important if you were born Thorin Goldhammer or if you later became part of the clan, what's important is that you're part of the clan.
So a dwarven city will indeed be held in its entirity by a single clan, more often than not. That does not, however, imply that all those dwarves share blood. Somebody who has married into the Stoneshaft clan is just as much as much a Stoneshaft as somebody who was born into it.
As to how these marriages come to be, it's often not really a marriage through romance. Races of Stone, the third edition D&D supplement that has a large amount of information on dwarves, mentions that arranged marriages are common, especially when it comes to interclan marriages. It mentions that
While marrying for love is not unknown, among very wealthy or prestigious families, it is often secondary to finding a suitable match that will further the well-being of the clan as a whole.
Marriage is also not something personal. From the same passage, we learn that
the parents of the prospective mates and the clan chieftain must approve every match before courtship can begin.
Failure to do so can result in fines and even exile for dwarves, who hold very strongly to traditions and the idea that the clan is more important than the individual.