1. they come from just normal inhabitants of Faeo, you know, craftsman, peasants, merchants, etc.,
it's during the war with Orc invasion, that people picked up weapons to defend Faeo, notice, this is about Faeo, both Magmar and human.
and after the war, these fighters have gained great skills of combat, so they dont want to go back to old business, they can do assassination or fight as mercenary.
2. and why are there 3 clans?
during a quest for the mermaids (rich merchant wants a mermaid captured for entertaining), the inner true nature caused the foundation of the clans:
Red Axe = Profit 1st, chop chop chop, u die, i collect trophy, quest done.
Stone Lotus = ethics 1st, some we do, some we don't, principle, order, wealth...
Night Stealers = old school mercs, honoring the war, and the relations built up, doing quests more like joint operations, with ethics too, call it united human and magmar merc then, cause they do well in chaos with coordination.