As a competing answer to the one of @MadaraUchiha, here's my take.
The clan belonging is solved quite easily. The clan-belonging is given through the generations maternally.
This means what decides the clan is not the father, but the mother. In Naruto's case that is Kushina Uzumaki
Other than that, the naruto-wiki gives some nice information:
A clan (一族, Ichizoku; Literally meaning "family"), in the loosest
sense of the term, refers to a family or group of shinobi who form a
basic unit of a shinobi village. Majority of these clans were mercenary military forces even before the First Shinobi World War. [...] Membership in a clan is usually determined by blood relations and genetics, which is vital in the usage of kekkei genkai and secret techniques. [...] While clans may be composed of many individuals and extended families, many clans mentioned and seen in the series were somewhat limited to a nuclear family.
Highlighting by me
It seems that the most clans seen, are just the mentioned nuclear families. This leads to the assumption, that one line of family that somewhen declared itself a clan is a clan. Some family lines had more offspring, and some had less. for example the Hyuuga-clan has multiple branch families, who are subordinate to the main family. The Uchiha clan on the other hand seems to just be loosely organized.
Some clans seem to have a definitive familiy head (Hyuuga, Akimichi, Nara). Other clans are not organized (Uchiha, Uzumaki, Inuzuka, [...]).
Clans mostly differ in chakra affinity and Kekkei Genkai, as well as battle style. In fact that seems to be the only thing shared in a clan. This Chakra affinity seems to be genetic, so that you are rather born into a clan than "join" it. It seems that not every person has his / her own clan, most prominent examples are probably Kakashi Hatake and Might Guy.