Sachverhalt:
A.
A.a. B._ (geb. 1976; Beschwerdegegnerin) und A._ (geb. 1964; Beschwerdeführer) sind die nicht verheirateten Eltern von C._ (geb. 2008) und D._ (geb. 2012). Beide Kinder stehen unter der alleinigen elterlichen Sorge der Mutter (zum Sohn vgl. Urteil 5A_89/2016 vom 2. Mai 2016) und für beide Kinder besteht eine Beistandschaft nach <ref-law>.
A.b. Ab Mai 2015 kam dem Kindsvater ein 14-tägliches Besuchsrecht am Wochenende zu. Mit Entscheid vom 20. Dezember 2016 sistierte die Kindes- und Erwachsenenschutzbehörde Dorneck-Thierstein/Thal-Gäu (KESB) den persönlichen Verkehr zwischen Vater und Kindern bis Ende 2016 und ordnete ab dem 1. Januar 2017 für ein halbes Jahr ein begleitetes Besuchsrecht von monatlich drei Stunden an (vgl. dazu Urteil 5A_457/2017 vom 4. Dezember 2017). Am 26. Oktober 2017 und am 16. März 2018 verlängerte die KESB das begleitete Besuchsrecht um jeweils sechs Monate. In dieser Zeit war es A._ ausserdem verboten, ausserhalb der Besuchszeiten mit den Kindern oder der Kindsmutter Kontakt aufzunehmen oder Dritte mit einer Kontaktaufnahme zu beauftragen.
A.c. Mit Entscheid vom 11. Dezember 2018 sistierte die KESB soweit hier interessierend jeglichen persönlichen Verkehr zischen A._ und den Kindern für die Dauer von mindestens zwölf Monaten und sah stattdessen quartalsweise Erinnerungskontakte vor. Ausserdem wies sie A._ unter Strafandrohung nach <ref-law> an, den Kontakt zu den Kindern in jeglicher Form (direkt oder indirekt) zu unterlassen. Weiter hielt die KESB fest, Anträge auf Wiederaufnahme des Kontaktrechts würden erst wieder geprüft, wenn der Kindsvater nachweise, dass er sich nachhaltig und seit mindestens vier Monaten einer Therapie unterziehe, um seine Rolle am Elternkonflikt zu beleuchten und zu verstehen und sich bewusst zu werden, auf welche Weise er das Kindeswohl schützen könne. Sodann ernannte die KESB eine neue Beistandsperson und legte deren Aufgabenbereich neu fest.
B.
Die von A._ hiergegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Solothurn mit Urteil vom 22. Juli 2019 (eröffnet am 24. Juli 2019) unter Kostenfolge ab.
C.
Mit Beschwerde in Zivilsachen vom 16. September 2019 gelangt A._ ans Bundesgericht und stellt die folgenden Anträge in der Sache:
"1. Das Urteil der Vorinstanz vom 22. Juli 2019 sei vollumfänglich aufzuheben.
1.1. Das Besuchsrecht [von A._] für C._ und D._ sei auf alle zwei Wochen von Freitagmittag, 12.00 Uhr, bis Sonntagabend, 19.00 Uhr, auszudehnen.
1.2. [A._] sei ein Ferienrecht für seine Kinder von mindestens 4 Wochen pro Jahr einzuräumen.
1.3. [A._] sei das Recht einzuräumen, mindestens einmal pro Woche mit den Kindern zu telefonieren.
2. Eventualiter sei die Sache zur Bestellung eines Kinderanwalts, zur Anhörung der Kinder durch eine unabhängige Fachperson, der Anordnung einer Mediation, der Anhörung von Frau E._ als sachverständige Zeugin und neuen Entscheidung an die KESB [...] zurück zu weisen.
3. Subeventualiter sei die Sache zur Bestellung eines Kinderanwalts, zur Anhörung der Kinder durch eine unabhängige Fachperson, zur Anordnung einer Mediation, zur Durchführung einer öffentlichen mündlichen Verhandlung mit Anhörung von Frau E._ als sachverständige Zeugin und neuen Entscheidung an die Vorinstanz zurück zu weisen.
4. Sub-subeventualiter sei die Sache zur Einholung eines systemischen Gutachtens unter Einbezug der Kinder zur Beurteilung der Anteile der Eltern an der Besuchsrechtsstreitigkeit, deren Erziehungsfähigkeit und der Umsetzung eines dem Kindeswohl entsprechenden Besuchs-, Ferien- und Kontaktrechts an die Vorinstanz zurück zu weisen."
Mit Verfügung vom 8. Oktober 2019 hat der Präsident der II. zivilrechtlichen Abteilung ein zwischenzeitlich gestelltes Gesuch von A._ um aufschiebende Wirkung der Beschwerde im Kostenpunkt abgewiesen. Am 23. Dezember 2019 reicht A._ weitere Unterlagen ein und ersucht um beförderliche Behandlung der Beschwerde. Am 18. Februar 2020 verzichtet die KESB auf eine Vernehmlassung. Gleichentags beantragt das Verwaltungsgericht, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Dieselben Anträge stellt B._ mit Vernehmlassung vom 5. März 2020. Mit Replik vom 20. März 2020 hält A._ an seinen bisherigen Anträgen fest. B._ hat mit Eingabe vom 31. März 2020 auf weitere Bemerkungen verzichtet. Im Übrigen hat das Bundesgericht die Akten des kantonalen Verfahrens eingeholt.

Erwägungen:
1.
1.1. Angefochten ist der Endentscheid (<ref-law>) eines oberen kantonalen Gerichts, das als Rechtsmittelinstanz (<ref-law>) über den persönlichen Verkehr zwischen den minderjährigen Kindern und dem nicht obhutsberechtigten Elternteil und damit eine nicht vermögensrechtliche Zivilsache nach <ref-law> entschieden hat. Die Beschwerde in Zivilsachen ist das zutreffende Rechtsmittel. Der Beschwerdeführer ist nach <ref-law> zur Beschwerde berechtigt (vgl. aber hinten E. 4.1), die er auch fristgerecht erhoben hat (Art. 100 Abs. 1; Art. 46 Abs. 1 Bst. b und <ref-law>). Auf die Beschwerde ist unter Vorbehalt der nachfolgenden Ausführungen einzutreten.
1.2. Mit der Beschwerde in Zivilsachen können Rechtsverletzungen gemäss Art. 95 f. BGG geltend gemacht werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>) und prüft mit freier Kognition, ob der angefochtene Entscheid Recht verletzt. Es befasst sich aber nur mit formell ausreichend begründeten Einwänden (vgl. <ref-law>). In der Beschwerdebegründung ist daher in gedrängter Form darzulegen, inwiefern der angefochtene Entscheid rechtswidrig sein soll. Die Begründung muss sachbezogen sein und sich auf den Streitgegenstand beziehen und beschränken; die beschwerdeführende Partei hat in gezielter Auseinandersetzung mit den für das Ergebnis des angefochtenen Entscheids massgeblichen Erwägungen plausibel aufzuzeigen, welche Rechte bzw. Rechtsnormen die Vorinstanz verletzt haben soll (<ref-ruling> E. 1.7.1; <ref-ruling> E. 2).
1.3. Was den Sachverhalt angeht, so legt das Bundesgericht seinem Urteil die vorinstanzlichen Feststellungen zugrunde (<ref-law>). Diesbezüglich kann nur vorgebracht werden, diese Feststellungen seien offensichtlich unrichtig, d.h. willkürlich, oder würden auf einer anderen Bundesrechtsverletzung im Sinne von <ref-law> (z.B. Verletzung von <ref-law> oder <ref-law>) beruhen. In der Beschwerde ist überdies darzutun, inwiefern die Behebung der gerügten Mängel für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG). Es gilt das strenge Rügeprinzip nach <ref-law>. Das Bundesgericht prüft daher nur klar und detailliert erhobene und, soweit möglich, belegte Rügen, während es auf ungenügend substanziierte Rügen und rein appellatorische Kritik am Sachverhalt nicht eintritt (<ref-ruling> E. 1.3.1, 317 E. 5.4; <ref-ruling> E. 2.3 S. 266). Tatfrage ist auch die Beweiswürdigung, womit die Anfechtung der diesbezüglichen vorinstanzlichen Feststellungen ebenfalls der qualifizierten Begründungspflicht unterliegt (Urteil 5A_438/2018 vom 30. Oktober 2018 E. 1.3; vgl. auch <ref-ruling> E. 4.1).
1.4. Neue Tatsachen und Beweismittel dürfen vor Bundesgericht nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>). Hiervon erfasst sind unechte Noven, also Tatsachen, die im bisherigen Verfahren bereits hätten vorgebracht werden können, aber nicht vorgebracht wurden. Echte Noven, d.h. Tatsachen, die erst entstanden sind, nachdem vor der Vorinstanz keine neuen Tatsachen und Beweismittel mehr vorgetragen werden konnten, sind im Verfahren vor Bundesgericht demgegenüber grundsätzlich unbeachtlich (<ref-ruling> E. 1.2; <ref-ruling> E. 3.1.2).
Die Verfahrensbeteiligten beziehen sich verschiedentlich auf Vorkomnisse, welche sich erst nach Ausfällung des angefochtenen Entscheids ereignet haben, und reichen zugehörige Unterlagen zu den Akten. Beispielhaft kann auf die vom Beschwerdeführer am 23. Dezember 2019 eingereichten Schreiben verschiedener Privatpersonen, darunter seiner Rechtsanwältin, verwiesen werden, in denen auf angebliche Kindeswohlgefährdungen durch die vorinstanzliche Regelung des persönlichen Verkehrs hingewiesen wird (act. 17). Alle diese echten Noven bleiben im Verfahren vor Bundesgericht unbeachtlich.
1.5. Der Beschwerdeführer beantragt die Aufhebung des gesamten angefochtenen Urteils. Er setzt sich indes nicht mit der Abweisung eines Gesuchs um Protokollberichtigung auseinander und äussert sich auch nicht zur im Übrigen von der Vorinstanz getroffenen prozessleitenden Anordnung. Auf diese Punkte ist nicht weiter einzugehen.
2.
2.1. Der Beschwerdeführer rügt vorab, die Vorinstanz habe den Sachverhalt "teils selektiv, tendenziös und grobe Mängel verdeckend zu [seinen] Lasten" festgestellt. In der Folge legt er die Geschehnisse seit dem Ende der Beziehung zwischen den Parteien im Jahr 2013 dar.
Mit seinen Ausführungen stellt der Beschwerdeführer seine Sicht der Dinge den tatsächlichen Feststellungen des Verwaltungsgerichts gegenüber ohne auch nur ansatzweise aufzuzeigen, inwiefern dieses den entscheidrelevanten Sachverhalt in einer Art und Weise (qualifiziert) fehlerhaft festgestellt hätte, welche durch das Bundesgericht zu berücksichtigen wäre. Der Beschwerdeführer verkennt das Wesen der Sachverhaltsbindung des Bundesgerichts und der Begründungsanforderungen an eine Sachverhaltsrüge (vgl. vorne E. 1.3). Er unterzieht die vorinstanzliche Sachverhaltsfeststellung einer umfassenden Kritik, als ob das Bundesgericht diese Feststellung wie eine Appellationsinstanz mit voller Kognition prüfen müsste, was gerade nicht der Fall ist (<ref-ruling> E. 4.1; Urteil 4A_627/2017 vom 28. Juni 2018 E. 3.2.2). Der Beschwerdeführer äussert sich sodann zu teilweise weit zurückliegenden Vorkommnissen, zeigt jedoch nicht auf, inwiefern diese für die heute noch strittigen Fragen von Relevanz wären. Auf die Beschwerde ist in diesem Umfang nicht einzutreten.
Im Übrigen missachtet der Beschwerdeführer, dass das Bundesgericht keine Beweismassnahmen trifft (vgl. statt vieler Urteil 5A_151/2018 vom 11. Juli 2018 E. 1.4), weshalb die Anträge auf Parteibefragung, Zeugeneinvernahmen und Anhörung der Kinder abgewiesen werden.
2.2. Der Beschwerdeführer erachtet sodann verschiedene einzeln genannte Feststellungen von Tatsachen durch die Vorinstanz als willkürlich (<ref-law>). Dazu führt er aus, die Kindsmutter verstehe es, "durch ihre Anwältin immer wieder [...] Anekdoten ins Verfahren einzubringen, was von den Behörden sofort übernommen wird, um den angeblichen Loyalitätskonflikt zu belegen. Die Wiedergabe der Kindsmutter ist nicht korrekt und unwahr". Freilich beschränkt der Beschwerdeführer sich darauf, seine eigene Darstellung der fraglichen Vorkommnisse und deren Würdigung den Feststellungen des Verwaltungsgerichts entgegen zu stellen und Letztere als willkürlich zu bezeichnen. Damit genügt er den an Sachverhaltsrügen zu stellenden Begründungsanfoderungen abermals nicht (vgl. vorne E. 1.3; zur Rüge der Verletzung des Willkürverbots vgl. <ref-ruling> E. 1.4.1; <ref-ruling> E. 2.2). Auf die Beschwerde ist auch insoweit nicht einzutreten.
3.
3.1. Der Beschwerdeführer macht weiter eine Verletzung von Art. 6 Ziff. 1 EMRK geltend, weil das Verwaltungsgericht keine öffentliche Verhandlung durchgeführt habe.
Diesbezüglich lässt sich dem angefochtenen Urteil entnehmen, dass der Beschwerdeführer bereits im vorinstanzlichen Verfahren die Durchführung einer öffentlichen Verhandlung beantragte. Das Verwaltungsgericht wies diesen Antrag ab und führte einzig eine nicht öffentliche Instruktionsverhandlung durch. Dem vorinstanzlichen Urteil lässt sich sodann nicht entnehmen, dass vor der KESB eine öffentliche Verhandlung stattgefunden hätte. Damit stellt sich die Frage von vornherein nicht, ob der Konventionsgarantie durch eine solche Verhandlung Rechnung getragen würde.
3.2. Die Vorinstanz hat richtig erkannt, dass der Beschwerdeführer gestützt auf Art. 6 Ziff. 1 EMRK grundsätzlich Anspruch auf eine (publikums-) öffentliche Verhandlung hat. Sodann haben weder die Parteien (ausdrücklich oder stillschweigend) auf eine derartige Verhandlung verzichtet, noch kann die Öffentlichkeit im vorliegenden hoheitlich geprägten Kindesschutzverfahren (für einen vergleichbaren Fall vgl. Urteil 5A_955/2015 vom 29. August 2015 E. 2.6 [elterliche Sorge]) pauschal mit Hinweis auf den in der Konventionsbestimmung als Ausnahmetatbestand vorgesehenen "Schutz des Privatlebens" vom Verfahren ausgeschlossen werden. Nichts anderes ergibt sich aus dem in der Zivilprozessordnung - diese ist auf Kindesschutzverfahren ohnehin nicht (direkt) anwendbar (<ref-law>; Art. 443 ff. und 450f ZGB) - vorgesehenen Ausschluss der Öffentlichkeit in familienrechtlichen Verfahren (<ref-law>), auf welchen die Beschwerdegegnerin sich beruft (vgl. Urteil 5A_522/2016 vom 14. März 2017 E. 2.2.3). Ein (ausnahmsweiser) Ausschluss der Öffentlichkeit bedarf vielmehr der besonderen Begründung (<ref-ruling> E. 2.2; <ref-ruling> E. 3.1.1). Strittig ist, ob die Vorinstanz ohne Konventionsverletzung eine derartige Ausnahme bejahen und auf die beantragte öffentliche Verhandlung verzichten durfte.
3.3. Ob ein besonderer Ausschlussgrund gegeben ist, beurteilt sich aufgrund der konkreten Umstände des Einzelfalls. Bei der im Rahmen dieses Entscheids vorzunehmenden Gewichtung und Abwägung der massgebenden Umstände steht dem Sachgericht ein gewisser Beurteilungsspielraum zu, in den das Bundesgericht nur mit Zurückhaltung eingreift (<ref-ruling> E. 2.6 mit zahlreichen Hinweisen).
Nach Darstellung des Verwaltungsgerichts versucht der Beschwerdeführer die Kinder in seinem Kampf gegen die Kindsmutter zu instrumentalisieren und zu manipulieren, was die Kinder in einen massiven Loyalitätskonflikt versetze und beim Sohn zu einer Anpassungsstörung geführt habe. Eine solch sensible familienrechtliche Angelegenheit sollte nicht in der Öffentlichkeit verhandelt werden. Erschwerend komme hinzu, dass der Beschwerdeführer auch mit dem Antrag auf eine öffentliche Verhandlung vorab eine "Hetzkampagne" gegen die Behörde führe, was vom Grundsatz der Justizöffentlichkeit nicht geschützt werde. Diesem Grundsatz komme vorliegend ohnehin nicht dieselbe Bedeutung zu wie etwa in einem Strafverfahren. Der Beschwerdeführer habe den Fall bereits in die Presse getragen, weshalb mit einem grossen Pressaufgebot zu rechnen wäre. Der Instruktionsrichter und die Gerichtsschreiberin hätten sich sodann an der Instruktionsverhandlung einen persönlichen Eindruck machen können. Alles in allem würde sich die dem Verfahren zugrunde liegende Problematik der Druckausübung auf die Kinder mit einer öffentlichen Verhandlung verstärken, was dem zu schützenden Kindeswohl zuwiderliefe. Die Interessen der Kinder an einem Ausschluss der Öffentlichkeit seien daher überwiegend. Die Beschwerdegegnerin verweist darauf, dem Kindsvater gehe es letztlich darum, "den Gerichtssaal zu füllen mit KESB-kritischen Personen, die gegen die Kindsmutter Stimmung machen sollen". Dies verdiene keinen Rechtsschutz.
Der Beschwerdeführer bestreitet "mit Vehemenz", dass sein Verhalten bei den Kindern einen Loyalitätskonflikt begründe und beim Sohn eine Anpassungsstörung verursache. Das von der Vorinstanz in diesem Zusammenhang zitierte Gutachten sei veraltet und auch die Kindsmutter und die Beiständin würden Entsprechendes nicht bestätigen. Die KESB fälle "unter dem Deckmantel" des Kindesschutzes Entscheide, die eines Rechtsstaats unwürdig seien und auch in der breiten Öffentlichkeit nicht verstanden würden. Daher sei eine öffentliche Kontrolle nötig. Der Druck auf die Kinder werde nicht durch ein öffentliches Verfahren, sondern die Kindsmutter erzeugt, welche ihnen den Zugang zum Vater verunmögliche. Die Kinder seien gesund und gut entwickelt und zeigten keine Verhaltensauffälligkeiten. Im Verfahren vor der KESB spielten Loyalitätskonflikte sodann immer eine Rolle, weshalb die Öffentlichkeit deswegen nicht ausgeschlossen werden dürfe, ansonsten kein "KESB Fall" öffentlich verhandelt werde. Verleumderisch sei die Behauptung, dem Beschwerdeführer gehe es nur darum, den Gerichtssaal mit KESB-kritischen Personen zu füllen.
3.4. Auch im vorliegenden Zusammenhang weicht der Beschwerdeführer von den vorinstanzlich festgestellten tatsächlichen Grundlagen ab, ohne hinreichend präzis eine offensichtlich unrichtige Sachverhaltsfeststellung zu rügen oder aufzuzeigen (vgl. dazu vorne E. 1.3). Der blosse Hinweis, ein Gutachten sei veraltet, reicht dazu nicht. Ausgehend von den tatsächlichen Feststellungen des Verwaltungsgerichts kann diesem sodann kein Rechtsfehler bei der Prüfung, ob ein besonderer Grund für den Ausschluss der Öffentlichkeit gegeben ist, vorgeworfen werden. Vielmehr hat es die massgebenden Kriterien (insbesondere Schutzbedürftigkeit der Kinder und Grundsatz der Justizöffentlichkeit) gemessen an den Umständen des Einzelfalls gewichtet und gegeneinander abgewogen (vgl. für einen ähnlichen Fall <ref-ruling> E. 2.6). Im Rahmen der vorzunehmenden Gesamtwürdigung hat das Verwaltungsgericht auch zutreffend die Problematik des Loyalitätskonflikts bei den Kindern berücksichtigt. Entgegen dem Beschwerdeführer ist dieses Kriterium sehr wohl zu beachten, auch wenn in Angelegenheiten des Kindesschutzes häufig ein Loyalitätskonflikt vorliegen dürfte. Alles andere widerspräche dem im Kindesschutzrecht zentralen Gedanken des Schutzes des Kindeswohls (vgl. <ref-law>).
Zusammenfassend konnte das Verwaltungsgericht ohne Konventionsverletzung von der Durchführung einer öffentlichen Verhandlung absehen und erweist die Beschwerde sich insoweit als unbegründet.
4.
4.1. Der Beschwerdeführer beanstandet sodann, dass die Vorinstanz keine Vertretung für die Kinder ernannte. Hierin liege eine Verletzung von <ref-law> sowie Art. 13 EMRK.
Vorab ist fraglich, ob der Beschwerdeführer diesbezüglich überhaupt zur Beschwerde in Zivilsachen berechtigt ist. Dies würde nach Art. 76 Abs. 1 Bst. b BGG ein eigenes schutzwürdiges Interesse an der Aufhebung oder Änderung des angefochtenen Entscheids im strittigen Punkt voraussetzten (Urteil 5A_542/2019 vom 30. Juli 2019 E. 3.1 mit zahlreichen Hinweisen). Der Beschwerdeführer ist nicht sorgeberechtigt und beruft sich bezüglich der Kindesvertretung vorwiegend auf die Interessen seiner Kinder (vgl. E. 4.4 hiernach). Indessen obliegt es dem sorgeberechtigten Elternteil oder einem Kindesvertreter, die Interessen des Kindes in das Verfahren einzubringen, und sieht <ref-law> anders als Art. 299 Abs. 2 Bst. b ZPO kein Antragsrecht der Elternteile vor. Damit ist nicht offensichtlich, dass der Beschwerdeführer zur Beschwerde gegen die Verweigerung einer Kindesvertretung legitimiert ist (vgl. Urteil 5A_278/2016 vom 6. Juni 2016 E. 1). Entgegen der ihn auch insoweit treffenden Pflicht zur Begründung der Beschwerde (<ref-ruling> E. 1.2; jüngst etwa Urteil 5A_542/2019 vom 30. Juli 2019 E. 3.1), äussert der Beschwerdeführer sich zu diesem Punkt nicht. Wie es sich hiermit im Einzelnen verhält, braucht mit Blick auf die nachfolgenden Ausführungen indes nicht entschieden zu werden:
4.2. Gemäss <ref-law> ordnet die Kindesschutzbehörde wenn nötig die Vertretung des Kindes an und bezeichnet als Beistand eine in fürsorgerischen und rechtlichen Fragen erfahrene Person. Diese Bestimmung auferlegt der Behörde, von Amtes wegen zu prüfen, ob dem Kind eine Vertretung in Form eines Beistands zur Seite zu stellen ist. Dies ist insbesondere der Fall, wenn die Eltern bezüglich wichtiger Fragen des persönlichen Verkehrs unterschiedliche Anträge stellen (<ref-law>). Auch in diesen Fällen besteht aber lediglich eine Prüfungspflicht der Behörde, selbst wenn ein Elternteil die Vertretung beantragt. Die Anordnung einer Kindesvertretung ist keineswegs zwingend; sie steht vielmehr im Ermessen der Behörde (Urteil 5A_403/2018 vom 23. Oktober 2018 E. 4.1.2 mit zahlreichen Hinweisen). Das Bundesgericht prüft einen derartigen Ermessensentscheid nur mit Zurückhaltung. Es greift nur ein, wenn die kantonale Instanz von dem ihr zustehenden Ermessen einen falschen Gebrauch gemacht hat, d.h. wenn sie grundlos von in Lehre und Rechtsprechung anerkannten Grundsätzen abgewichen ist, wenn sie Gesichtspunkte berücksichtigt hat, die keine Rolle hätten spielen dürfen, oder wenn sie umgekehrt rechtserhebliche Umstände ausser Acht gelassen hat. Aufzuheben und zu korrigieren sind ausserdem Ermessensentscheide, die sich im Ergebnis als offensichtlich unbillig oder als in stossender Weise ungerecht erweisen (<ref-ruling> E. 4.5; <ref-ruling> E. 11.2).
4.3. Das Verwaltungsgericht hält fest, es sei unbestritten, dass die Kinder ihren Vater gerne sehen möchten. Welchen Zusatznutzen eine Kindesvertretung bringen würde, sei daher unklar. Insbesondere obliege die Beurteilung, ob der subjektive Wille der Kinder auch ihren objektiven Interessen entspreche, nicht der Vertretung des Kindes, sondern dem Gericht. Dieses entscheide zudem im Kindeswohl und in Anwendung des Untersuchungsgrundsatzes. Der Beschwerdeführer zeige nicht auf, welche zusätzlichen entscheidrelevanten Erkenntnisse durch eine Kindesvertretung gewonnen werden könnten. Vielmehr belasse er es bei allgemeinen Ausführungen zum Thema. Die Kinder würden ausserdem durch die bereits ernannte Beiständin ausreichend vertreten. Von Letzterem geht auch die Kindsmutter aus.
4.4. Der Beschwerdeführer äussert sich auch vor Bundesgericht vorab in allgemeiner Art und Weise zur Kindesvertretung und führt insbesondere aus, diese erfülle die "prozessuale Funktion [...], dem Gericht das objektivierte Kindeswohl zu vermitteln". Hiermit vermag er von vornherein keine rechtsfehlerhafte Ermessensausübung durch die Vorinstanz aufzuzeigen.
Sodann verweist der Beschwerdeführer auf das Urteil 5A_618/2016 vom 26. Juni 2017 (in: FamPra.ch 2017 S. 1148), wonach sich die Anordnung einer Kindesvertretung regelmässig dann erübrige, wenn der Inhaber der elterlichen Sorge eine anwaltliche Vertretung des urteilsunfähigen Kindes bestellen könne. Dies sei jedoch nur möglich, wenn das Vertretungsrecht des Sorgerechtsinhabers nicht wegen eines Interessenkonflikts ausgeschlossen sei (<ref-law>; Urteil, a.a.O., E. 2.2.2). Vorliegend besteht nach Dafürhalten des Beschwerdeführers "klarerweise eine Kollision zwischen den Interessen der Kinder und der Mutter". Letztere informiere die Kinder noch nicht einmal altersgerecht über das laufende Verfahren und lasse sie über ihre Mitwirkungsmöglichkeiten im Unklaren. Damit sei der Zusatznutzen der Kindesvertretung aufgezeigt. Indes handelt es sich bei der Feststellung, wonach ein klarer Konflikt zwischen den Interessen der Mutter und der Kinder bestehe, um eine blosse Behauptung des Beschwerdeführers. Das Verwaltungsgericht hat Entsprechendes nicht festgehalten und der Beschwerdeführer erhebt auch in diesem Punkt nicht die notwendigen Rügen, damit das Bundesgericht vom vorinstanzlichen Sachverhalt abweichen könnte (vgl. vorne E. 1.3). Seine entsprechenden Ausführungen bleiben daher unbeachtlich.
Unter diesen Umständen vermag der Beschwerdeführer die Ermessensausübung der Vorinstanz nicht in Frage zu stellen. Dies gilt auch für das weitere Argument, wonach die Ernennung einer Kindesvertretung die Kompromissbereitschaft der Eltern erhöhen würde. Selbst wenn dies zutreffen sollte, erwiese sich das angefochtene Urteil deswegen nicht als rechtsfehlerhaft. Nichts anderes ergibt sich weiter aus dem pauschalen Hinweis auf Art. 13 EMRK, zumal der Beschwerdeführer entgegen der ihn auch diesbezüglich treffenden strengen Begründungspflicht (<ref-law>; vgl. Urteil 5A_305/2018 vom 15. Mai 2018 E. 3.2 mit Hinweis auf <ref-ruling> E. 2) nicht ausführt, inwieweit die Konventionsbestimmung im vorliegenden Kontext über das Gesetz hinausgehen würde oder verletzt sein sollte (vgl. dazu auch Urteil 5A_232/2016 vom 6. Juni 2016 E. 4). Die Beschwerde erweist sich mit Blick auf die Kindesvertretung damit als unbegründet, sofern überhaupt auf sie einzutreten ist. Damit ist entgegen dem Beschwerdeführer auch nicht entscheidend, dass die für die Überwachung des Besuchsrechts eingesetzte Beiständin, anders als die Vorinstanz und die Beschwerdegegnerin meinen, nicht als Kindesvertreterin nach <ref-law> auftreten kann (Urteil 5A_400/2015 vom 25. Februar 2016 E. 2.3, nicht publiziert in: <ref-ruling>, aber in: FamPra.ch 2016 S. 772).
5.
5.1. Nach Ansicht des Beschwerdeführers verstösst die Vorinstanz weiter gegen <ref-law> sowie Art. 12 des Übereinkommens vom 20. November 1989 über die Rechte des Kindes (Kinderrechtskonvention, KRK; SR 0.107), indem sie seinen Antrag auf Anhörung der Kinder durch eine unabhängige Fachperson abgewiesen hat.
Die Kindesanhörung wird für das Verfahren vor der Kindesschutzbehörde in <ref-law> geregelt. Diese Bestimmung konkretisiert die entsprechenden Ansprüche gemäss <ref-law>, Art. 6 Ziff. 1 EMRK und Art. 12 KRK. Die Anhörung des Kindes ist zum einen Ausfluss seiner Persönlichkeit und dient zum anderen der Sachverhaltsfeststellung. Nach der Rechtsprechung ist die Anhörung im Sinn einer Richtlinie ab dem vollendeten sechsten Altersjahr möglich, wobei es nicht ausgeschlossen ist, je nach den konkreten Umständen auch ein etwas jüngeres Kind anzuhören, etwa wenn bei Geschwistern das jüngere Kind kurz vor dem genannten Schwellenalter steht (<ref-ruling> E. 1.2.3). Während bei älteren Kindern der persönlichkeitsrechtliche Aspekt im Vordergrund steht und das Kind ein eigenes Mitwirkungsrecht hat, ist die Anhörung bei kleineren Kindern im Sinne eines Beweismittels zu verstehen, weshalb die Eltern die Anhörung des Kindes als solches beantragen können (<ref-ruling> E. 1.1). Die Anhörung findet jedoch grundsätzlich unabhängig von Anträgen, d.h. von Amtes wegen statt. Soweit entsprechende Anträge vorhanden sind, besteht unter Vorbehalt der vom Gesetz genannten wichtigen Gründen umso mehr eine Verpflichtung zur Durchführung der Anhörung (<ref-ruling> E. 1.2 und 1.4; zum Ganzen: Urteil 5A_809/2018 vom 18. Dezember 2019 E. 3.3 mit zahlreichen Hinweisen). Eine mehrmalige Anhörung kann dort unterbleiben, wo sie einzig um der Anhörung willen stattfände, namentlich wenn sie für das Kind eine unnötige Belastung bedeuten würde, wie etwa bei akuten Loyalitätskonflikten, und überdies keine neuen Erkenntnisse zu erwarten wären. Um eine solche Anhörung um der Anhörung willen zu vermeiden, besteht die Pflicht, ein Kind anzuhören, in der Regel nur einmal im Verfahren, und zwar grundsätzlich nicht nur auf die einzelne Instanz gesehen, sondern einschliesslich Instanzenzug. Ein Verzicht auf eine erneute Anhörung setzt allerdings voraus, dass das Kind zu den entscheidrelevanten Punkten befragt worden und das Ergebnis der Anhörung noch aktuell ist (zum Ganzen Urteile 5A_914/2018 vom 18. Dezember 2019 E. 3.3.1; 5A_721/2018 vom 6. Juni 2019 E. 2.4.1; je mit zahlreichen Hinweisen). Sind die Voraussetzungen für die Anhörung eines Kindes gegeben, so lässt diese sich nicht durch eine antizipierte Beweiswürdigung umgehen (Urteil 5A_70/2017 vom 11. September 2017 E. 4.2 mit Hinweisen).
5.2. Das Verwaltungsgericht hält fest, C._ sei (einzig) vor etwas mehr als vier Jahren im Rahmen einer Begutachtung und D._ gar nie durch die Behörden angehört worden. Dennoch habe die Sichtweise der Kinder zur konkreten Fragestellung des Besuchsrechts detailliert Eingang in das Verfahren gefunden. Es sei denn auch nicht strittig, dass die Kinder den Vater gerne öfters und unbegleitet sehen würden. Damit würde eine Anhörung bloss um der Anhörung willen erfolgen, was gerade im vorliegenden Fall, wo der Loyalitätskonflikt der Kinder zentral sei, nicht zum Wohl der Kinder wäre. Eher gegen eine Anhörung spreche auch, dass die Fähigkeit zur autonomen Willensbildung bei Kindern erst etwa ab dem 12. Altersjahr vorhanden sei. Die Nichtanhörung verletze damit weder die Pflicht zur Sachverhaltsermittlung noch das Mitwirkungsrecht der Kinder. Auch die Beschwerdegegnerin ist der Ansicht, dass eine Anhörung der Kinder nichts an dem vorinstanzlichen Entscheid ändern würde, da der Wunsch der Kinder, den Vater zu sehen, nicht bestritten sei. Ausserdem sei das Bundesgericht bereits im Urteil 5A_457/2017 vom 4. Dezember 2017 zum Schluss gelangt, die Einschätzung der Vorinstanz sei von der Kinderbefragung unabhängig und eine Anhörung um der Anhörung willen sei zu vermeiden (E. 4.1.2).
5.3. Wie der Beschwerdeführer richtig vorbringt, wendet das Verwaltungsgericht die massgebende Grundsätze fehlerhaft an:
Mit Blick auf das Alter der Kinder, die im Zeitpunkt des vorinstanzlichen Urteils rund sieben bzw. elf Jahre alt waren, war das Verwaltungsgericht nach dem in E. 5.1 hiervor Ausgeführten grundsätzlich gehalten, diese von Amtes wegen anzuhören. Dazu hat umso mehr Anlass bestanden, als ein entsprechender Antrag vorliegt. Entgegen der Vorinstanz liegt sodann kein Grund vor, um (ausnahmsweise) auf die Anhörung zu verzichten. Vorab darf diese nicht mit der Begründung ausgeschlossen werden, der Standpunkt der Kinder habe bereits Eingang in das Verfahren gefunden, worin eine antizipierte Beweiswürdigung liegt (zum Begriff der antizipierten Beweiswürdigung vgl. <ref-ruling> E. 9.3.2). Damit braucht auch nicht geprüft zu werden, ob die in diesem Zusammenhang getroffene Feststellung zutrifft, wonach die Kinder sich zur Frage des Besuchsrechts bereits in das Verfahren haben einbringen können. Unbestritten ist die Tochter im laufenden Verfahren sodann noch gar nicht und der Sohn nur einmal vor vier Jahren angehört worden. Mit Blick auf das Alter des Jungen (ca. elf Jahre im Zeitpunkt des vorinstanzlichen Entscheids) kann keine Rede davon sein, dass seine Anhörung heute noch aktuell ist (vgl. <ref-ruling> E. 5; Urteil 5A_266/2017 vom 29. November 2017 E. 6.3 [beide betreffend Gutachten]). Eine (aktuelle) Anhörung der Kinder hat damit nicht stattgefunden. Die beantragte Anhörung lässt sich folglich auch nicht gestützt auf die Rechtsprechung ausschliessen, wonach zur Vermeidung unzumutbarer Belastungen Anhörungen um der Anhörung willen zu vermeiden sind. Nach dem Ausgeführten liegen heute andere Verhältnisse vor, als dies bei Ausfällung des Urteils 5A_457/2017 vom 4. Dezember 2017 der Fall war. Dort hielt das Bundesgericht noch fest, der Verzicht auf die Anhörung der Tochter sei nicht zu beanstanden, da diese noch nicht einmal fünf Jahre alt sei. Die vom Sohn anlässlich seiner Anhörung getätigten Aussagen seien ebenfalls noch aktuell (E. 4.1.2). An dieser Beurteilung kann heute nicht mehr festgehalten werden, weshalb die Kindsmutter sich vergeblich auf dieses Urteil beruft. Sofern vorliegend überhaupt zu berücksichtigen (vgl. vorne E. 1.4), bleibt zuletzt auch der Hinweis auf eine offenbar ausserhalb des laufenden Verfahrens vorgenommene und nicht weiter dokumentierte Anhörung der Kinder durch die Beiständin unbehelflich (vgl. Urteil 5A_411/2014 vom 3. Februar 2014 E. 2.2; vgl. auch Urteil 5A_575/2017 vom 17. August 2017 E. 2.3).
5.4. Die Beschwerde erweist sich damit in diesem Punkt als begründet und sie ist in Aufhebung der Ziffer 3 des angefochtenen Urteils gutzuheissen. Das Unterlassen des gehörigen Einbezugs der Kinder in das Verfahren hat die Aufhebung des Entscheids in der Sache zur Folge. Der Beschwerdeführer beantragt die Rückweisung der Angelegenheit an die KESB, da ihm ansonsten eine Instanz verloren gehe und dies sachgerechter als die Rückweisung an die Vorinstanz sei. Ersteres mag zwar zutreffen. Indes kann das Verwaltungsgericht die sich noch stellenden Fragen mit voller Kognition beurteilen (<ref-law>). Auch besteht ein erhebliches Interesse daran, über die Ausgestaltung des persönlichen Verkehrs zwischen dem Vater und den Kindern baldmöglichst Klarheit zu schaffen. Dem würde die Rückweisung an die erste Instanz entgegenstehen. Der Beschwerdeführer legt sodann nicht weiter dar, weshalb das Verwaltungsgericht die Anhörung nicht sollte durchführen können. Die Angelegenheit ist daher zur Anhörung der Kinder und zum erneuten Entscheid an dieses zurückzuweisen (<ref-law>). Der Beschwerdeführer begründet sodann seinen Antrag nicht, die Anhörung habe durch eine unabhängige Fachperson zu erfolgen. Hierauf ist folglich nicht weiter einzugehen und es bleibt dem die Befragung durchführenden Gericht überlassen, wie es die Anhörung im Einzelnen ausgestaltet (vgl. <ref-ruling> E. 4; <ref-ruling> E. 4.4.2; Urteile 5A_701/2011 vom 12. März 2012 E. 2.2.2, in: FamPra.ch 2012 S. 821; 5A_229/2011 vom 8. August 2011 E. 5.2, in: FamPra.ch 2011 S. 1026).
Mangels Zuständigkeit des Bundesgerichts nicht einzutreten ist auf das Gesuch des Beschwerdeführers, einzelne Mitglieder des vorinstanzlichen Spruchkörpers hätten im Fall der Rückweisung der Sache an das Verwaltungsgericht für das weitere Verfahren in den Ausstand zu treten (<ref-law>; <ref-law> i.V.m. § 145 Abs. 1 des Gesetzes [des Kantons Solothurn] vom 4. April 1954 über die Einführung des Schweizerischen Zivilgesetzbuches [EG ZGB; BGS 211.1], § 8 Abs. 1 des Gesetzes [des Kantons Solothurn] vom 15. November 1970 über den Rechtsschutz in Verwaltungssachen [Verwaltungsrechtspflegegesetz; BGS 124.11] sowie § 98 Abs. 1 Bst. d des Gesetzes [des Kantons Solothurn] vom 13. März 1977 über die Gerichtsorganisation [GO; BGS 125.12]).
6.
6.1. Nach dem Ausgeführten erübrigt es sich, auf die Ausführungen des Beschwerdeführers zur Ausgestaltung des persönlichen Verkehrs zwischen ihm und seinen Kindern einzugehen. Ebenso wenig braucht der Antrag auf Einholung eines systemischen Gutachtens behandelt zu werden, den der Beschwerdeführer nur für den Fall stellt, dass keine Kindesanhörung verfügt wird. Nachfolgend sind aber die weiteren Rügen zu behandeln, welche unabhängig vom Ausgang des Verfahrens in der Sache beurteilt werden können.
6.2. Einzugehen ist vorab auf das Vorbringen des Beschwerdeführers, das Verwaltungsgericht habe die Untersuchungsmaxime nach Art. 314 Abs. 1 i.V.m. <ref-law> verletzt. Dies gilt jedenfalls insoweit, als der Beschwerdeführer nicht auch diesen Vorwurf mit der unterlassenen Anhörung der Kinder begründet. Insoweit macht er geltend, das Verwaltungsgericht habe nicht auf ein veraltetes Gutachten aus dem Jahre 2015 abstellen dürfen.
Im Prinzip ist zwar richtig, dass sich die Verhältnisse bei kleinen Kindern schnell verändern können, sodass bereits eine Begutachtung, die erst zwei Jahre zurückliegt, überholt sein kann (<ref-ruling> E. 5; Urteil 5A_1033/2017 vom 21. Juni 2018 E. 4.3 a.E.). Indes müsste der Beschwerdeführer nach der Rechtsprechung zunächst aufzeigen, dass das Gericht den Sachverhalt willkürlich festgestellt hat, bevor er sich erfolgreich auf eine Verletzung der Untersuchungsmaxime berufen kann (Urteile 5A_994/2018 vom 29. Oktober 2019 E. 6.2.6.3; 5A_103/2018 und 5A_111/2018 vom 6. November 2016 E. 3.1; je mit Hinweisen). Diesem Erfordernis vermag die Beschwerde mit dem blossen Hinweis darauf, die Vorinstanz habe auf ein zu altes Gutachten abgestellt, nicht zu genügen (vgl. vorne E. 1.3). Soweit der Beschwerdeführer in der Replik sodann auf eine angebliche Befangenheit der Gutachtensperson hinweist, ist ihm entgegenzuhalten, dass er den Ausstandsgrund unverzüglich hätte geltend machen müssen (vgl. <ref-ruling> E. 2.4; <ref-ruling> E. 3.2.1). Ohnehin muss die Begründung in der Beschwerde enthalten sein und sind nach Ablauf der Beschwerdefrist eingereichte Beschwerdeergänzungen unzulässig. Die Replik dient einzig dazu, sich zur gegnerischen Stellungnahme zu äussern (<ref-ruling> E. 1.2.3; Urteil 5A_626/2018 vom 3. April 2019 E. 3.2, nicht publ. in: <ref-ruling>). Auf die Beschwerde ist insoweit nicht einzutreten.
6.3. Der Beschwerdeführer beanstandet weiter, dass das Verwaltungsgericht einen Antrag um Verpflichtung der Eltern zu einer Mediation abgewiesen und die Anordnung der KESB aufrechterhalten hat, wonach auf Eingaben erst wieder eingegangen werde, wenn der Beschwerdeführer den Besuch einer Therapie nachweise (vgl. vorne Bst. A.c).
6.3.1. Die Anordnung der KESB betreffend den Besuch einer Therapie verstösst nach Dafürhalten des Beschwerdeführers gegen <ref-law> und verletzt seine Persönlichkeitsrechte. Tatsächlich erscheint die Verknüpfung der Anhandnahme weiterer Gesuche mit dem Besuchen einer Therapie mit Blick auf die allgemeinen Verfahrensgarantien und insbesondere das Verbot der Rechtsverweigerung und den Anspruch auf rechtliches Gehör als problematisch (Art. 29 Abs. 1 und 2 BV und dazu <ref-ruling> E. 4.2; <ref-ruling> E. 2.3). Der Beschwerdeführer erhebt hierzu indes keinerlei Rügen, womit er den an die Beschwerde in Zivilsachen zumal hinsichtlich der Rüge der Verletzung von Grundrechten zu stellenden strengen Rüge- und Begründungsanforderungen nicht gerecht wird (<ref-law>; <ref-ruling> E. 5.1; <ref-ruling> E. 2.4; Urteil 5A_694/2016 vom 31. März 2017 E. 3). Soweit der Beschwerdeführer sodann gestützt auf <ref-law> eine Verletzung seiner Persönlichkeitsrechte geltend macht, verkennt er, dass die Bestimmungen des Zivilgesetzbuches zum Schutz der Persönlichkeit einzig auf die Beziehung unter Privaten, nicht jedoch auf diejenige zwischen Privaten und dem Staat, wie sie hier in Frage steht, Anwendung finden (BGE <ref-ruling> E. 3.1 und 3.2; Urteil 2C_37/2018 vom 15. August 2018 E. 8).
6.3.2. Sodann erläutert der Beschwerdeführer, weshalb der Streit zwischen den Eltern über das Besuchsrecht nicht "einseitig durch Repressionen gegen die Kinder und ihren Vater gelöst werden" könne, sondern durch Anordnung einer Mediation zwischen den Eltern. Dabei solle "in Hinblick auf das Zusammenwirken der Eltern mit Bezug auf die Kinderbelange nach Lösungen" gesucht werden. Der angefochtene Entscheid verletzte <ref-law> und Art. 18 KRK. Das Verwaltungsgericht hält demgegenüber dafür, in der gegebenen Situation verspreche nicht eine Mediation zwischen den Eltern, sondern eine Therapie des Beschwerdeführers Erfolg. Auch die Kindsmutter erachtet eine Mediation nicht als erfolgsversprechend.
Gemäss <ref-law> kann die Kindesschutzbehörde den Eltern Weisungen für die Pflege, Erziehung oder Ausbildung erteilen. Gestützt auf diese Bestimmung ist die Behörde namentlich befugt, Weisungen zur Durchführung einer Therapie oder einer Mediation zu erlassen, wobei unter Mediation in diesem Sinne eine Gesprächstherapie zwischen den Eltern zwecks Verbesserung der Kommunikation zu verstehen ist (Urteil 5A_522/2017 vom 22. November 2017 E. 4.7.3.2). Vorausgesetzt ist eine Gefährdung des Wohls des Kindes und dass die Eltern nicht von sich aus für Abhilfe sorgen oder hierzu nicht in der Lage sind. Ausserdem muss die Massnahme zum Schutz des Kindeswohls geeignet, das mildeste erfolgversprechende Mittel und der betroffenen Person zumutbar sein (<ref-law>; <ref-law>). Die Kindesschutzbehörde verfügt bei der Auswahl und Anordnung der zu treffenden Massnahme über einen grossen Ermessensspielraum (Urteil 5A_887/2017 vom 16. Februar 2018 E. 5.1 mit Hinweisen), in welchen das Bundesgericht nur mit Zurückhaltung eingreift (vgl. vorne E. 4.2).
Der Beschwerdeführer legt in einiger Ausführlichkeit dar, weshalb die Unstimmigkeiten zwischen den Eltern seiner Ansicht nach mit Mediationsgesprächen bei einem erfahrenen Mediator aufgelöst werden könnten. Seine Ausführungen sind indessen appellatorisch gehalten. Ausserdem weicht er auch in diesem Zusammenhang von den tatsächlichen Feststellungen der Vorinstanz ab, ohne dies weiter zu begründen, womit er mit den entsprechenden Vorbringen nicht zu hören ist (vgl. vorne E. 1.3). Damit gelingt es ihm mit Blick auf das Ermessen der Behörden nicht, die auf einem willkürfrei festgestellten Sachverhalt (vgl. vorne E. 2) gründenden Ausführungen der Vorinstanz als rechtsfehlerhaft erscheinen zu lassen. Zur Anordnung der Therapie erhebt er sodann keine weiteren Einwände, namentlich macht er nicht geltend, diese würde ihn unzumutbar hart treffen. Zwar führt er aus, die Anordnung einer Therapie sei "völlig unverhältnismässig" und "geradezu willkürlich". Er begründet indes nicht, wie er zu dieser Einschätzung gelangt, womit er damit nicht zu hören ist. Auch in diesem Zusammenhang äussert sich der Beschwerdeführer sodann nicht näher dazu, inwieweit die Kinderrechtskonvention verletzt sein sollte oder deren Garantien über die gesetzliche Regelung hinausgehen sollten (vgl. vorne E. 4.4).
6.3.3. Folglich erweist sich die Beschwerde auch hinsichtlich des Gesuchs um Durchführung einer Mediation und der Anordnung einer Therapie als unbegründet, soweit darauf einzutreten ist.
6.4. Zuletzt rügt der Beschwerdeführer, dass die Vorinstanz es zu Unrecht abgelehnt habe, E._ als sachverständige Zeugin anzuhören. Vorab fällt auf, dass der Beschwerdeführer mit keinem Wort erwähnt, welche Rechts- oder Verfassungsnorm die Vorinstanz deswegen verletzt haben solle. Abgesehen davon beschränkt er sich auch in diesem Zusammenhang darauf, seine eigene Einschätzung der Sach- bzw. Rechtslage den Ausführungen des Verwaltungsgerichts entgegenzustellen, welches zum Schluss gelangte, die beantragte Befragung würde nichts am Beweisergebnis ändern Auch insoweit vermag die Beschwerde den Begründungserfordernissen folglich nicht zu genügen (vorne E. 1.3) und es ist nicht darauf einzutreten.
7.
7.1. Zusammenfassend ist die Beschwerde teilweise gutzuheissen, soweit darauf einzutreten ist, und ist die Ziffer 3 des angefochtenen Urteils aufzuheben. Die Sache ist zur Anhörung der Kinder und zum erneuten Entscheid über den persönlichen Verkehr an das Verwaltungsgericht zurückzuweisen. Dieses wird ausserdem neu über die Kosten des kantonalen Verfahrens zu entscheiden haben, weshalb auch die Ziffern 4 und 5 des angefochtenen Urteils aufzuheben sind. Weitergehend ist die Beschwerde abzuweisen.
Die Beschwerdegegnerin beantragt, es sei eine Medienmitteilung zum vorliegenden Urteil zu veröffentlichen. Das Bundesgericht entscheidet über die Veröffentlichung seiner Urteile von Amtes wegen. Ein Recht auf Urteilsveröffentlichung besteht nicht (Urteil 5F_8/2018 vom 5. März 2019 E. 4, nicht publ. in: <ref-ruling>). Auf das Gesuch der Beschwerdegegnerin ist nicht einzutreten. Ohnehin besteht kein Anlass für den Erlass einer Medienmitteilung (vgl. <ref-law> i.V.m. Art. 57 Abs. 1 Bst. d des Reglements vom 20. November 2006 für das Bundesgericht [BGerR; SR 173.110.131]).
7.2. Bei diesem Ausgang des Verfahrens obsiegt der Beschwerdeführer zu einem Fünftel. Dementsprechend sind die Kosten des bundesgerichtlichen Verfahrens diesem zu vier Fünfteln und der Beschwerdegegnerin zu einem Fünftel aufzuerlegen (Art. 66 Abs. 1 und 2 BGG). Der Beschwerdeführer hat der Beschwerdegegnerin ausserdem eine reduzierte Parteientschädigung auszurichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Soweit darauf eingetreten wird, wird die Beschwerde teilweise gutgeheissen und werden die Ziffern 3-5 des Urteils des Verwaltungsgerichts des Kantons Solothurn vom 22. Juli 2019 aufgehoben. Die Sache wird zur Anhörung der Kinder und zum erneuten Entscheid über den persönlichen Verkehr an das Verwaltungsgericht zurückgewiesen. Weitergehend wird die Beschwerde abgewiesen.
2.
Die Gerichtskosten von Fr. 3'000.-- werden im Umfang von Fr. 2'400.-- dem Beschwerdeführer und im Umfang von Fr. 600.-- der Beschwerdegegnerin auferlegt.
3.
Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2'100.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien, dem Verwaltungsgericht des Kantons Solothurn, der Kindes- und Erwachsenenschutzbehörde Thal-Gäu/ Dorneck-Thierstein und der Beiständin schriftlich mitgeteilt.
Lausanne, 4. Mai 2020
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Herrmann
Der Gerichtsschreiber: Sieber