Das hängt sehr stark davon ab, wann und wo es stattfand. Ganz unumstritten sind die Mechanismen unter Historikern auch nicht immer. Man denke da nur an die Geschichte mit den 'Königsfreien' der Karolinger. Aber im Prinzip kann man sagen: das System funktionierte mehr oder weniger nach dem Subsidiaritätsprinzip. Die (Oh, Mist, Terminologie...) Magnaten, Barone, Fürsten, nenn es, wie Du willst, sind ihrem König Gefolgschaft schuldig. Das ist eine ziemlich universelle Tatsache, auch wenn es immer mal wieder Beispiele gegeben hat, bei denen das im Einzelfall in Abrede gestellt wurde. Im Fall eines Krieges wendet sich der Herrscher an diese Leute und fordert sie auf, ihm mit Truppen beizustehen. Die sind dann wiederum in der Verantwortung, diese Truppen zu besorgen. Das können ihre eigenen Lehnsnehmer, Gefolgsleute, Mitglieder ihres Haushaltes oder angeworbene Soldaten sein.
Im Detail kann das aber sehr unterschiedlich aussehen. In karolingischer zeit z.B. ist es gebräuchlich, dass sich die Großen des reiches auf Aufforderung mit Truppenkontingenten an einem bestimmten Ort einfinden (dem Märzfeld, später auch Maifeld), wo der König sie erwartet und in den Krieg führt. Das setzt natürlich voraus, dass der König einen Angriffskrieg führt, was unter den Karolingern recht üblich war. Es ist unbekannt ob es festgelegte Kontingente gab, und Schätzungen über die Größe des Heeres gehen weit auseinander. Zudem ist auch bekannt, dass es einen Mechanismus gab, nach dem Landbesitzer persönlich dem König zur Heerfolge verpflichtet waren, aber es ist eher unwahrscheinlich, dass sie für die Feldzüge jedesmal aufgerufen wurden. Vermutlich diente dies System eher der Verteidigung. Geklärt ist das aber alles lange noch nicht.
Unter Ottonen und Saliern galt ein prinzipiell ähnliches System, nach dem aber von bestimmten Funktionären der Reichsverwaltung (Bischöfen, Äbten, Grafen) festgelegte Kontingente von 'loricati' zu stellen waren. Ein Problem hier ist, dass es nicht ganz klar ist, ob diese Kontingente je voll ausgeschöpft wurden oder ob es sich um theoretische Werte handelte. Anzunehmen ist aber, dass es zumindest theoretisch möglich war, und dass es sich bei den 'loricati' um Lehnsnehmer und kleine Grundbesitzer handelte.
Das spätere Lehnswesen (pace, Reynolds) entwickelt dann komplizierte Strukturen, die regeln, wer wem unter welchen Umständen Heerfolge schuldig ist. Das ist ganz besonders eine Spezialität im Hl. Römischen Reich. In anderen Teilen Europas spielt das schon eine wesentlich weinger wichtige Rolle. In Teilen der Mittelmeerwelt spielen z.B. städtische milizen eine größere Rolle, für die alle erwachsenen männlichen Bürger verpflichtet werden konnten, die aber im Normalfall nur kleine Kontingente von jungen Männern ins Feld schickten. Kastilien, Aragon und Sizilien z.B. setzen sehr stark auf solche Truppen. Das gibt es später auch im Norden, aber die Städte sind hier meist militärisch weniger wichtig.
Söldner ist ein schwieriger Begriff. Was man besonders in der Zeit vor 1000 nicht unterschätzen sollte ist die Rolle von direkten Gefolgsleuten, Kämpfern, die dem Haushalt ihres Herrn angehörten. Die stehen natürlich immer zur Verfügung, leben davon, dass sie kämpfen (könnten), und erhalten von ihren Herrn Lohn. Als Söldner würde ich sie nicht bezeichnen. Auch der klassische Topos des 'fahrenden Ritters' des Hochmittelalters kann durchaus als ein Mehrzwecksoldat auf der Suche nach einem Arbeitgeber betrachtet werden. Das ziel ist hier natürlich der erwerb eines Lehens, aber als was beueichnet man ihn in der Zeit davor? Besonders wenn es um Leute wie die berüchtigten 'Flamen' und 'Brabanzonen' geht, die sich im 11. und 12. Jh. in großen Scharen gegen Geld zur Verfügung stellen. Solche Truppen kamen wohl auf eigene Initiative zu einem kriegführenden Fürsten oder wurden bewußt angeworben.
Auch später gibt es immer wieder Grenzfälle. z.B. ist nach englischem Recht jeder freie Mann heerfolgepflichtig. Zum Krieg werden aber von den Magnaten und Städten bestimmte Kontingente angeworben, und die bekommen Sold. Sie würden sich aber selbst kaum als Söldner im selben Sinn betrachtet haben wie z.B. die genuesen, die für den französischen König kämpften. Hier war das Prinzip übrigens eine Mischung von 'feudalen' und 'modernen' Traditionen: die Lehnsnehmer erhalten vom König den Aufruf zum Krieg und rekrutieren nun 'auf dem freien Arbeitsmarkt' Truppenkontingente zum Aufstocken ihrer persönlichen Gefolgsleute. Das 'reine' Söldnersystem (wie z.B. der Landsknechte) gibt es auch, zunächst parallel, später (besonders in Süd- und Zentraleuropa) fast ausschliesslich.
Und dann gibt es noch gefolgschaftspflichtige Stämme bzw. angeworbene Ausländer und ethnische Minderheiten (nach den verschiedensten Prinzipien organisiert), Militärsklaven, und Freiwillige, die sich einem Krieg anschliessen, weil si sich Beute erhoffen, Ruhm ernten wollen, oder religiöse Pflichten erfüllen wollen. Im Extremfall (z.B. bei der Preußenreise, aber auch bei z.B. den Murabitun) sind das Leute, die dafür bezahlen, in den Krieg ziehen zu dürfen.
Es ist jedenfalls relativ kompliziert. Aber im allgemeinen galt meist, dass Herrscher Ansprechpartner auf der nächstniedrigen Hierarchieebene hatten, die ihnen ihrerseits Truppen besorgten, wen sie die brauchten. Söldner konnten zusätzlich angeworben werden, und kluge Könige hatten meist auch ihre eigenen unmittelbaren Gefolgsleute. Und die Intewrpretation der Quellen ist nicht immer einfach. Frag bei Gelegenheit mal einen Fachmann, was man unter 'liberi homines' und 'vassi' zu verstehen hat.