Sachverhalt:
A.
A.a. Die A._ Football Association (Beschwerdeführerin) ist der nationale Fussballverband von A._. Sie ist Mitglied der Fédération Internationale de Football Association (FIFA) mit Sitz in der Schweiz.
B._ (Beschwerdegegner) ist professioneller Fussballtrainer mit Staatsangehörigkeit von U._.
Die A._ Football Association und B._ schlossen am 16. September 2015 einen Vertrag, betitelt mit "Coaching Service Contract for Women's National Team of [A._ Football Association]". Demzufolge wurde B._ für eine Dauer von 4 Jahren als Trainer der Fussballnationalmannschaft der Frauen von A._ engagiert.
Am 25. Oktober 2017 entband die A._ Football Association B._ mündlich von seiner Funktion als Trainer. Am 9. März 2018 teilte sie ihm schriftlich mit, dass sie den Vertrag vorzeitig auflöse.
A.b. B._ leitete am 26. April 2018 bei der Kommission für den Status von Spielern (Players' Status Committee) der FIFA (nachfolgend: FIFA-Kommission) ein Verfahren gegen die A._ Football Association ein. Er trug vor, die A._ Football Association habe den Vertrag ohne zureichenden Grund beendet, und beantragte, die A._ Football Association sei zu verurteilen, ihm USD 1'106'250.-- netto für die Restlaufzeit des Vertrags, USD 420'000.-- netto für voraussichtlich erzielte Anreizprämien und USD 100'000.-- als Genugtuung zu bezahlen. Ausserdem verlangte er eine öffentliche Entschuldigung der A._ Football Association.
Die A._ Football Association bestritt die Zuständigkeit der FIFA-Kommission. Sie vertrat die Auffassung, B._ habe seine Ansprüche in A._ geltend zu machen, und zwar zunächst bei der "X._ Arbitration Commission" und in der Folge allenfalls beim "Y._ Court".
Mit Entscheid vom 27. März 2020 erklärte die FIFA-Kommission (respektive deren Einzelrichter) die Klage für zulässig und hiess sie teilweise gut. Die Kommission verurteilte die A._ Football Association, B._ USD 1'106'250.-- zu bezahlen. Die weiteren von B._ gestellten Anträge wurden abgewiesen. Zur Begründung der Zuständigkeit stützte sich der Einzelrichter auf Art. 22 lit. c (in Verbindung mit Art. 23) des FIFA-Reglements bezüglich Status und Transfer von Spielern, wonach die FIFA-Kommission für internationale arbeitsrechtliche Streitigkeiten zwischen einem Verband und einem Trainer zuständig sei.
B.
Am 19. Juni 2020 erklärte die A._ Football Association beim Tribunal Arbitral du Sport (TAS) Berufung gegen diesen Entscheid. Sie berief sich unter anderem auf die (angebliche) Unzuständigkeit der FIFA-Kommission.
Mit Schiedsentscheid vom 26. Mai 2021 wies der Einzelschiedsrichter des TAS die Berufung ab und bestätigte den angefochtenen Entscheid. Er kam namentlich zum Ergebnis, dass die FIFA-Kommission ihre Zuständigkeit zur Beurteilung der Klage von B._ zu Recht bejaht habe.
C.
Die A._ Football Association verlangt mit Beschwerde in Zivilsachen vom 24. Juni 2021, der Schiedsentscheid des Einzelschiedsrichters des TAS vom 26. Mai 2021 sei aufzuheben. Die Zuständigkeit der FIFA-Kommission sowie des TAS "zur Beurteilung der Streitsache" sei "zu verneinen". Eventualiter sei die Angelegenheit an das TAS zur Neubeurteilung der Zuständigkeit der FIFA-Kommission zurückzuweisen.
Die von der Beschwerdeführerin gestellten Gesuche um Erteilung der aufschiebenden Wirkung und um Vereinigung des Verfahrens mit dem konnexen Beschwerdeverfahren 4A_346/2021 wurden mit Präsidialverfügung vom 25. Juni 2021 abgewiesen beziehungsweise betreffend Vereinigung der Verfahren derzeit abgewiesen. Die Instruktion der Verfahren erging koordiniert.
Der Beschwerdegegner beantragt, auf die Beschwerde nicht einzutreten. Eventualiter sei sie abzuweisen. Das TAS verzichtete auf Vernehmlassung, unter Hinweis auf den angefochtenen Schiedsentscheid. Die Beschwerdeführerin replizierte, worauf der Beschwerdegegner eine Duplik eingereicht hat.
Mit Präsidialverfügung vom 7. September 2021 verpflichtete das Bundesgericht die Beschwerdeführerin - wie vom Beschwerdegegner beantragt - zur Sicherstellung einer allfälligen Parteientschädigung im Umfang von Fr. 17'000.--. Diese wurde fristgemäss an die Bundesgerichtskasse geleistet.

Erwägungen:
1.
Eine Vereinigung der Verfahren 4A_344/2021 und 4A_346/2021 erfolgt definitiv nicht, da sowohl die Beschwerdegegner als auch die angefochtenen Entscheide verschieden sind.
2.
Nach <ref-law> ergeht der Entscheid des Bundesgerichts in einer Amtssprache, in der Regel in jener des angefochtenen Entscheids. Wurde dieser in einer anderen Sprache abgefasst, bedient sich das Bundesgericht der von den Parteien verwendeten Amtssprache. Der angefochtene Entscheid ist in englischer Sprache abgefasst. Da es sich dabei nicht um eine Amtssprache handelt, ergeht der Entscheid des Bundesgerichts praxisgemäss in der Sprache der Beschwerde (<ref-ruling> E. 1).
3.
Der Sitz des Schiedsgerichts befindet sich in Lausanne. Die Parteien hatten im massgebenden Zeitpunkt ihren Sitz beziehungsweise Wohnsitz ausserhalb der Schweiz. Da sie die Geltung des 12. Kapitels des IPRG nicht ausdrücklich ausgeschlossen haben, gelangen dessen Bestimmungen zur Anwendung (siehe Art. 176 Abs. 1 und 2 IPRG). Die Beschwerde in Zivilsachen ist somit unter den Voraussetzungen der Art. 190-192 IPRG (SR 291) zulässig (<ref-law>).
4.
Der Schiedsentscheid kann nur aus einem der in <ref-law> abschliessend aufgezählten Gründe angefochten werden. Nach <ref-law> prüft das Bundesgericht nur die Rügen, die in der Beschwerde vorgebracht und begründet worden sind; dies entspricht der in <ref-law> für die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht vorgesehenen Rügepflicht (<ref-ruling> E. 5 mit Hinweis).
5.
5.1. Die Beschwerdeführerin moniert auch vor Bundesgericht, die FIFA-Kommission sei für die Beurteilung der Streitsache nicht zuständig gewesen, und beruft sich auf <ref-law>. Nach dieser Bestimmung kann ein Schiedsentscheid angefochten werden, wenn sich "das Schiedsgericht zu Unrecht für zuständig oder unzuständig erklärt hat".
5.2. Bei verbandsinternen Entscheidungsorganen handelt es sich nach ständiger bundesgerichtlicher Rechtsprechung nicht um Schiedsgerichte. Ihre Entscheidungen stellen einfache Willensäusserungen der beteiligten Vereine - und nicht etwa Rechtsprechungsakte - dar (<ref-ruling> E. 3b S. 276; Urteile 4A_612/2020 vom 18. Juni 2021 E. 4 [Entscheid, nicht aber diese Erwägung, zur Publikation vorgesehen]; 4A_476/2020 vom 5. Januar 2021 E. 3.2; 4A_490/2017 vom 2. Februar 2018 E. 3.3.4; 4A_432/2017 vom 22. Januar 2018 E. 3.3; 4A_492/2016 vom 7. Februar 2017 E. 3.3.3; 4A_222/2015 vom 28. Januar 2016 E. 3.2.3.1; 4A_374/2014 vom 26. Februar 2015 E. 4.3.2.1). Dies gilt auch für die hier in Frage stehende FIFA-Kommission (vgl. <ref-ruling> E. 2.2.1 S. 349; Urteil 4A_222/2015 vom 28. Januar 2016 E. 3.2.3.1).
Derartige Entscheidungen von Organen eines Vereins schweizerischen Rechts können - sofern der vereinsinterne Instanzenzug ausgeschöpft ist - gestützt auf <ref-law> angefochten werden, und zwar entweder vor dem zuständigen staatlichen Gericht oder - bei Vorliegen einer entsprechenden Schiedsvereinbarung oder Schiedsklausel - vor einem verbandsunabhängigen Schiedsgericht, wie namentlich dem TAS (<ref-ruling> E. 1.2.2; <ref-ruling> E. 2.2.1; Urteile 4A_612/2020 vom 18. Juni 2021 E. 4 [Entscheid, nicht aber diese Erwägung, zur Publikation vorgesehen]; 4A_600/2016 vom 29. Juni 2017 E. 3.2.1; siehe auch Urteil 5A_1027/2018 vom 22. Juli 2019 E. 4). Vor Bundesgericht kann in diesem Zusammenhang gestützt auf <ref-law> geltend gemacht werden, das Schiedsgericht (etwa das TAS) habe sich zu Unrecht für die Beurteilung einer solchen Anfechtungsklage zuständig oder unzuständig erklärt.
5.3. Bei der Entscheidung der FIFA-Kommission vom 27. März 2020 handelt es sich um den Beschluss eines Organs eines schweizerischen Vereins. Das TAS stützte seine Kompetenz zur Beurteilung der gegen diesen Beschluss gerichteten Anfechtungsklage auf Art. 57 f. der FIFA-Statuten, Ausgabe 2019, welche die Zuständigkeit des TAS für Berufungen gegen letztinstanzliche Entscheide der FIFA (insbesondere deren Rechtsorgane) vorsehen, und ferner auf Art. R47 TAS-Code. Letzterer hält fest, dass - unter gewissen Voraussetzungen - beim TAS Berufung gegen die Entscheidung eines Verbands erhoben werden kann, wenn dies in den Statuten oder Reglementen des betreffenden Verbands vorgesehen ist. Die Beschwerdeführerin bestreitet weder die Gültigkeit der Schiedsklausel in den FIFA-Statuten noch ihre Bindung daran. Sie anerkennt, dass das TAS vorliegend - auch in sachlicher Hinsicht - die zuständige Anfechtungsinstanz im Sinne von <ref-law> ist; insbesondere behauptet sie nicht, die vereinsintern letztinstanzliche Entscheidung der FIFA-Kommission vom 27. März 2020 hätte vor einem Gericht aus A._ oder sonst einem staatlichen Gericht angefochten werden müssen. Die Beschwerdeführerin hat denn auch selbst die Entscheidung der FIFA-Kommission an das TAS weitergezogen.
5.4. Wenn die Beschwerdeführerin unter Hinweis auf den "Coaching-Service-Vertrag" vom 16. September 2015 und ihre eigenen Statuten nun vorträgt, die verbandsinterne FIFA-Kommission sei zur Beurteilung des Streits nicht kompetent gewesen, übergeht sie, dass vor Bundesgericht einzig hätte gerügt werden können, das Schiedsgericht (also das TAS) habe sich zu Unrecht für die Beurteilung der auf <ref-law> gestützten Anfechtungsklage zuständig erklärt (<ref-law>). Eine inhaltliche Überprüfung des angefochtenen Schiedsentscheids nimmt das Bundesgericht dagegen nur unter Ordre-public-Gesichtspunkten vor (<ref-law>). Eine Verletzung fundamentaler Rechtsgrundsätze macht die Beschwerdeführerin nicht geltend.
5.5. Wohl rügt die Beschwerdeführerin in allgemeiner Weise in Rz. 8 und 86 der Beschwerde, das TAS habe "seine eigene Zuständigkeit zur materiellen Entscheidung in der Sache" zu Unrecht bejaht, und sie stellt vor Bundesgericht das Begehren, auch die Zuständigkeit des TAS sei "zu verneinen". Sie begründet diese Rüge und diesen Antrag in der Beschwerde jedoch nicht weiter, worauf der Beschwerdegegner zu Recht aufmerksam macht. Damit hat es sein Bewenden.
6.
Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Ausgang des Verfahrens wird die Beschwerdeführerin kosten- und entschädigungspflichtig (siehe Art. 66 Abs. 1 und Art. 68 Abs. 1 und 2 BGG). In den beiden konnexen Verfahren 4A_344/2021 und 4A_346/2021 stimmen sowohl die Beschwerdeschriften als auch die Vernehmlassungen der jeweiligen (durch die gleichen Rechtsanwältinnen vertretenen) Beschwerdegegner über weite Strecken wörtlich überein. Es rechtfertigt sich daher, die grundsätzlich in Abstimmung auf die erhobene Gerichtsgebühr festgesetzte Parteientschädigung leicht zu reduzieren. Sie ist aus der an die Bundesgerichtskasse geleisteten Sicherheit auszurichten.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 15'000.-- werden der Beschwerdeführerin auferlegt.
3.
Die Beschwerdeführerin hat den Beschwerdegegner für das bundesgerichtliche Verfahren mit Fr. 13'600.-- zu entschädigen. Diese Entschädigung wird aus der an die Bundesgerichtskasse bezahlten Sicherheitsleistung ausgerichtet. Der Restbetrag von Fr. 3'400.-- wird der Beschwerdeführerin zurückerstattet.
4.
Dieses Urteil wird den Parteien und dem Tribunal Arbitral du Sport (TAS) schriftlich mitgeteilt.
Lausanne, 13. Januar 2022
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Kiss
Der Gerichtsschreiber: Stähle