@lightningcat
Some of the "noble" families would have their genesis in some tough guy with a bigger club. Whether these people were bandits or just another local, we wouldn't know, as it typically happened in pre-history times.
Once some of these families were established others could join through patronage, marriage & favour. Conquest was an occasional alternative.
Over time systems were put in place (feudalism, manorialism) to maintain the hierarchical structures.