Sachverhalt:
A.
A.a. A._ (Beschwerdeführer) und B._ (Beschwerdegegnerin) sind die nicht miteinander verheirateten Eltern der beiden Söhne C._ (geb. 2005) und D._ (geb. 2009). Die Kinder werden hauptsächlich von der Mutter betreut, das Sorgerecht üben beide Elternteile gemeinsam aus.
A.b. Am 23. September 2016 gelangte A._ mit einer Gefährdungsmeldung an die Kindes- und Erwachsenenschutzbehörde Thal-Gäu/Dorneck-Thierstein (nachfolgend: KESB) und machte geltend, die Kindsmutter befinde willkürlich über die Besuchszeiten. Für die Dauer des daraufhin eröffneten Verfahrens räumte die KESB dem Vater im Sinne einer vorsorglichen Massnahme das Recht ein und auferlegte ihm die Pflicht, die Söhne jedes zweite Wochenende von Freitagabend, 18.00 Uhr, bis Sonntagabend, 18.00 Uhr, jeden Mittwoch ab Schulschluss bis 19.30 Uhr sowie während der Hälfte der Schulferien zu betreuen.
Am 2. Mai 2018 gab die KESB den Kindseltern Gelegenheit, neue Anträge zur Reglung des persönlichen Verkehrs zwischen Vater und Söhnen zu stellen. Ohne Gegenbericht werde anhand der Akten undentsprechend der vorsorglichen Regelung entschieden. Nachdem beide Elternteile sich hatten vernehmen lassen, bestimmte die KESB am 31. Juli 2018, dass die Kinder je zwei Nachmittage im Monat mit dem Vater verbringen.
B.
Die hiergegen von A._ erhobene Beschwerde wies das Verwaltungsgericht des Kantons Solothurn mit Urteil vom 10. Januar 2019 (eröffnet am 16. Januar 2019) ab. Die Prozesskosten auferlegte es A._, dem es indes die unentgeltliche Rechtspflege bewilligte.
Am 13. November 2018 hatte die KESB die Kinder während laufendem Beschwerdeverfahren "im Rahmen eines Wiedererwägungsverfahrens" persönlich zum Besuchsrecht angehört.
C.
Am 5. Februar 2019 gelangt A._ mit Beschwerde in Zivilsachen an das Bundesgericht und stellt in der Sache die folgenden Anträge:
"1. Es sei der persönliche Verkehr zwischen den Kindern und dem Kindsvater wie folgt zu regeln:
1.1. Die Kinder verbringen jedes zweite Wochenende von Freitag 18:00 Uhr bis Sonntag 18:00 Uhr, sowie jeden Mittwoch ab Schulschluss bis um 19:30 Uhr beim Kindsvater.
1.2. Die Kinder verbringen 3 Wochen Ferien im Jahr beim Kindsvater.
1.3. Die Kinder verbringen die Hälfte der Feiertage beim Kindsvater.
1.4. Im Falle einer Widerhandlung gegen diese Regelung wird den Kindseltern eine Bestrafung nach Art. 292 StGB angedroht.
2. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.
3. Es sei dem Beschwerdeführer die unentgeltliche Rechtspflege mit dem Unterzeichneten als unentgeltlicher Rechtsbeistand zu gewähren."
Mit Vernehmlassung vom 6. Juni 2019 beantragt das Verwaltungsgericht unter Hinweis auf den angefochtenen Entscheid und die Akten die Abweisung der Beschwerde, soweit darauf eingetreten werden könne. B._ verweist in ihrer Eingabe vom 13. Juni 2019 ebenfalls auf den angefochtenen Entscheid und die Akten, stellt aber keinen Antrag in der Sache. Die KESB hat sich innert Frist nicht zur Sache vernehmen lassen und am 26. Juni 2019 hat der Instruktionsrichter ein Gesuch um Fristverlängerung abgewiesen.
Im Übrigen hat das Bundesgericht die Akten des kantonalen Verfahrens eingeholt.

Erwägungen:
1.
1.1. Angefochten ist der Endentscheid (Art. 90 BGG) eines oberen kantonalen Gerichts, das als Rechtsmittelinstanz (Art. 75 BGG) über den persönlichen Verkehr zwischen minderjährigen Kindern und dem nicht obhutsberechtigten Elternteil und damit eine nicht vermögensrechtliche Zivilsache nach Art. 72 Abs. 1 BGG entschieden hat. Die Beschwerde in Zivilsachen ist das zutreffende Rechtsmittel. Der Beschwerdeführer ist nach Art. 76 Abs. 1 BGG zur Beschwerde berechtigt, die er auch fristgerecht erhoben hat (Art. 100 Abs. 1 BGG). Auf die Beschwerde ist einzutreten.
1.2. Mit der Beschwerde in Zivilsachen können Rechtsverletzungen nach Art. 95 f. BGG geltend gemacht werden. Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). In der Beschwerde ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (Art. 42 Abs. 2 BGG; <ref-ruling> E. 2). Die Verletzung verfassungsmässiger Rechte prüft das Bundesgericht nur insofern, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (Art. 106 Abs. 2 BGG). Dabei gelten gesteigerte Rüge- und Begründungserfordernisse (dazu: <ref-ruling> E. 1.2.2; <ref-ruling> E. 2.4).
Das Bundesgericht ist an den vorinstanzlich festgestellten Sachverhalt gebunden (Art. 105 Abs. 1 BGG). Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig, d.h. willkürlich, ist oder auf einer Rechtsverletzung nach Art. 95 BGG beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrensentscheidend ist (Art. 97 Abs. 1 BGG; Art. 105 Abs. 2 BGG; <ref-ruling> E. 2).
2.
Umstritten ist die Ausgestaltung des persönlichen Verkehrs zwischen dem Beschwerdeführer und den Kindern der Parteien.
2.1. Das Verwaltungsgericht erwägt, die Kinder seien dreizeneinhalb (C._) bzw. bald zehn Jahre (D._) alt und damit in einem Alter, in dem sie zu autonomer Willensbildung fähig seien und ihr Wille dem Grundsatz nach zu berücksichtigen sei. Beide Kinder hätten klar und unmissverständlich zum Ausdruck gebracht, dass sie keinen weitergehenden Kontakt zum Kindsvater als den derzeit gelebten wünschten. Diesem Kindeswillen sei zurzeit Rechnung zu tragen. Ein entgegen dem kategorischen Willen und starken Widerstand der Kinder erzwungener Kontakt zum Vater sei weder mit dem Zweck des Umgangsrechts noch dem Persönlichkeitsrecht der Kinder vereinbar und widerspreche dem Kindeswohl. Auch sei die Anwendung direkten Zwangs oder Drucks abzulehnen, da dies dem Sinn und Zweck des Verkehrsrechts widerspreche und für dessen Ausübung kontraproduktiv sei. Einem weitergehenden Besuchsrecht des Vaters stünde aber nicht nur der Kindeswille, sondern auch der hochproblematische Umgang der Kindeseltern untereinander entgegen, der zu einem Loyalitätskonflikt für die Kinder führe. Eine stufenweise Ausdehnung des Besuchsrechts bis zu einem gerichtsüblichen Ausmass sei indes anzustreben.
2.2. Nach Ansicht des Beschwerdeführers hat zwar C._ gegebenenfalls die Fähigkeit, sich zum persönlichen Verkehr mit dem Vater einen autonomen Willen zu bilden. Beim erst neunjährigen D._ sei dies indes nicht der Fall. Jedenfalls hätten beide Kinder eher aber eine gewisse Gleichgültigkeit gegenüber dem Kontakt mit dem Vater zum Ausdruck gebracht, indes keine klare Weigerungshaltung an den Tag gelegt. Von einer eindeutigen und konstanten Willenskundgebung, die weitergehenden Besuchen des Vaters entgegenstehe, könne daher keine Rede sein. Indem das Verwaltungsgericht die Einschränkung des Besuchsrechts dennoch mit dem Kindeswillen begründe, verfalle sie in Willkür. Unbestritten liege sodann zwar ein Elternkonflikt vor. Weder von der Mutter noch den Kindern sei indes jemals geltend gemacht worden, das Kindeswohl werde durch häufigeren Kontakt zum Vater ernsthaft gefährdet. Die Mutter möchte vorab die Kinder zu nichts zwingen. Ein gewisser Druck sei indessen notwendig, schon nur, weil das Besuchsrecht nicht im freien Belieben der Söhne stehe.
2.3. Nach Art. 273 Abs. 1 ZGB haben Eltern, denen die elterliche Sorge oder Obhut nicht zusteht, und das minderjährige Kind gegenseitig Anspruch auf angemessenen persönlichen Verkehr. Dabei handelt es sich um ein gegenseitiges Pflichtrecht, das in erster Linie den Interessen des Kindes dient (<ref-ruling> E. 4a; <ref-ruling> E. 3a). Oberste Richtschnur für die Ausgestaltung des persönlichen Verkehrs ist das Kindeswohl (<ref-ruling> E. 5; vgl. auch <ref-ruling> E. 5.4). Damit hat das Gericht in Beachtung aller konkreter Umstände nach der für das Kind bestmöglichen Lösung zu suchen (<ref-ruling> E. 3; <ref-ruling> E. 4a; Urteil 5A_745/2015 vom 15. Juni 2016 E. 3.2.2.2). Die Interessen der Eltern haben hinter dem vorrangig massgebenden Kindeswohl zurückzustehen (<ref-ruling> E. 2.1; <ref-ruling> E. 3b). Wird das Wohl des Kindes durch den persönlichen Verkehr gefährdet, kann den Eltern das Recht auf diesen verweigert oder entzogen werden (Art. 274 Abs. 2 ZGB). Eine Gefährdung des Kindeswohls liegt vor, wenn die ungestörte körperliche, seelische oder sittliche Entfaltung des Kindes durch ein auch nur begrenztes Zusammensein mit dem nicht obhutsberechtigten Elternteil bedroht ist (Urteil 5A_875/2017 vom 6. November 2018 E. 3.3, in: FamPra.ch 2019 S. 243). Bei der Beschränkung des persönlichen Verkehrs ist stets das Gebot der Verhältnismässigkeit zu beachten. So darf dieser in der Regel nicht allein wegen elterlicher Konflikte dauerhaft eingeschränkt werden, jedenfalls soweit das Verhältnis zwischen dem nicht hauptbetreuenden Elternteil und dem Kind gut ist (<ref-ruling> E. 2.2.1; Urteil 5A_514/2018 vom 20. Februar 2019 E. 4.3.2).
Der Wille des Kindes ist eines von mehreren Kriterien beim Entscheid über den persönlichen Verkehr (Urteil 5A_875/2017 vom 6. November 2018 E. 3.3, in: FamPra.ch 2019 S. 243; vgl. auch Urteil 5A_463/2017 vom 10. Juli 2018 E. 4.5.5, nicht publiziert in: <ref-ruling>). Es steht aber nicht im freien Belieben des Kindes, ob es persönliche Kontakte zum nicht betreuenden Elternteil wünscht oder nicht; dies gilt namentlich dort, wo die ablehnende Haltung wesentlich durch die Einstellung des anderen Elternteils geprägt ist (<ref-ruling> E. 4a; Urteile 5A_522/2017 vom 22. November 2017 E. 4.6.3; 5A_459/2015 vom 13. August 2015 E. 6.2.2, in: Pra 2017 Nr. 19 S. 186; 5A_160/2011 vom 29. März 2011 E. 4, in: FamPra.ch 2011 S. 740). Bei der Berücksichtigung des Kindeswillens ist das Alter des Kindes bzw. dessen Fähigkeit zu autonomer Willensbildung zu berücksichtigen. Vom Vorliegen dieser Fähigkeit ist ungefähr ab dem 12. Altersjahr auszugehen (Urteile 5A_875/2017 vom 6. November 2018 E. 3.3, in: FamPra.ch 2019 S. 243; 5A_367/2015 vom 12. August 2015 E. 5.1.3, in: FamPra.ch 2015 S. 970; 5A_200/2015 vom 22. September 2015 E. 7.2.3.1, in: FamPra.ch 2016 S. 302; 5A_890/2014 vom 11. Februar 2015 E. 2.3.2). Lehnt das Kind den nicht betreuenden Elternteil ab, ist im Einzelfall zu prüfen, worin diese Haltung begründet liegt und ob die Ausübung des Besuchsrechts den Interessen des Kindes tatsächlich widerspricht. Dabei ist anerkannt, dass aufgrund des schicksalhaften Eltern-Kind-Verhältnisses die Beziehung des Kindes zu beiden Elternteilen sehr wichtig ist und bei dessen Identitätsfindung eine entscheidende Rolle spielen kann (<ref-ruling> E. 2.2.2 mit Hinweisen; Urteil 5A_745/2015 vom 15. Juni 2016 E. 3.2.2.2). Nur wo das urteilsfähige Kind den Umgang mit einem Elternteil aufgrund seiner Erfahrungen mit dem persönlichen Verkehr kategorisch verweigert, ist dieser Umgang aus Gründen des Kindeswohls auszuschliessen, weil ein gegen den starken Widerstand erzwungener Besuchskontakt mit dem Zweck des Umgangsrechts im Allgemeinen ebenso unvereinbar ist wie mit dem Persönlichkeitsschutz des Kindes (<ref-ruling> E. 2b; Urteile 5A_875/2017 vom 6. November 2018 E. 3.3, in: FamPra.ch 2019 S. 243; 5A_459/2015 vom 13. August 2015 E. 6.2.2, in: Pra 2017 Nr. 19 S. 186; 5C.250/2005 vom 3. Januar 2006 E. 3.2.1, in: FamPra.ch 2006 S. 751).
Das Besuchsrecht wird nach richterlichem Ermessen festgesetzt (Art. 4 ZGB; <ref-ruling> E. 3; Urteil 5A_962/2018 vom 2. Mai 2019 E. 5.2.1). Bei der Prüfung solcher Ermessensentscheide übt das Bundesgericht eine gewisse Zurückhaltung, greift aber namentlich dort ein, wo die kantonale Instanz grundlos von in Lehre und Rechtsprechung anerkannten Grundsätzen abgewichen ist (<ref-ruling> E. 3.2.5; <ref-ruling> E. 11.2).
2.4. Die KESB sah ein bloss minimales Kontaktrecht des Vaters zu den Söhnen vor, was das Verwaltungsgericht vorab unter Hinweis darauf stützte, dass die Kinder keinen weitergehenden Kontakt wünschten.
Diesbezüglich verweist der Beschwerdeführer zu Recht auf das Alter von D._; dieser war im Zeitpunkt des angefochtenen Urteils noch nicht ganz zehn Jahre alt, was auch das Verwaltungsgericht so feststellt (vgl. vorne Bst. A.a). Damit hat er das 12. Lebensjahr noch nicht erreicht, ab dem davon auszugehen ist, dass ein Kind zur Bildung eines autonomen Willens über die Ausgestaltung des persönlichen Verkehr fähig ist. Die Praxis spricht neun- bis zehnjährigen Kindern die Urteilsfähigkeit mit Blick auf die Frage der Ausgestaltung des Kontakts zu den Eltern denn auch vielfach ab (vgl. etwa Urteile 5A_322/2014 vom 14. Juli 2014 E. 5.3; 5A_92/2009 vom 22. April 2009 E. 5.1.2, in: FamPra.ch 2009 S. 786). Weshalb dies bei D._ anders sein sollte, führt das Verwaltungsgericht nicht aus. Es beschränkt sich auf den allgemeinen und nach dem Ausgeführten unzutreffenden Hinweis, das Kind sei in einem Alter, in dem es sich mitteilen und seine Meinung vertreten, d.h. auch darüber entscheiden könne, ob es Kontakt zum Vater haben wolle oder nicht.
Wie es sich hiermit im Einzelnen verhält, braucht indes nicht geklärt zu werden, da dem Beschwerdeführer auch darin zuzustimmen ist, dass es an einer klaren und konstanten Willensäusserung der Kinder fehlt, welche ausgedehnteren Kontakten mit dem Vater entgegensteht: Wie das Verwaltungsgericht festhält, hat D._ angegeben, er wolle den Vater "eigentlich nicht öfter sehen". Er, d.h. das Kind, sei häufig in der Schule und wolle am Wochenende zu Hause sein. Wenn es sein müsse, würde er aber öfters zum Vater gehen; allerdings nicht gerne. Einen Grund für seine Haltung vermochte der Knabe nicht anzugeben; "zuhause sei es einfach besser". C._ wiederum hat gemäss den Feststellungen der Vorinstanz erklärt,
"er wolle eigentlich nicht öfters zum Vater, es stimme so für ihn. Wenn er gehen müsse, dann würde er dies tun, aber er habe gar keine Lust dazu und wolle weiterhin spontan abmachen."
In diesen Aussagen kommt eine gewisse Gleichgültigkeit bzw. Unlust gegenüber Kontakten mit dem Vater zum Ausdruck. Eine kategorische Verweigerung weitergehender Besuche oder ein starker Widerstand gegen solche kann dagegen nicht festgestellt werden. Dies wäre nach der Rechtsprechung aber notwendig, damit sich eine Einschränkung des Besuchsrechts aus diesem Grund rechtfertigt. Entsprechend findet auch die Schlussfolgerung des Verwaltungsgerichts keine Stütze im festgestellten Sachverhalt, aufgrund der Weigerungshaltung der Kinder sei die Durchführung eines weitergehenden persönlichen Verkehrs mit dem Vater nicht mit dem Kindeswohl vereinbar. Die blosse Unlust der Kinder, den Vater öfters zu sehen, und deren Wunsch nach Flexibilität bei der Ausgestaltung des persönlichen Verkehrs vermögen hieran nichts zu ändern. Das Verwaltungsgericht ist daran zu erinnern, dass es sich beim persönlichen Verkehr zwischen dem Beschwerdeführer und den Söhnen um ein Pflichtrecht handelt. Auch wenn den Interessen der Kindes bei dessen Ausgestaltung grosse Bedeutung zukommt, steht die Ausgestaltung des persönlichen Verkehrs gerade nicht im freien Belieben der Kinder.
2.5. Die Festlegung eines bloss minimalen Kontaktrechts zwischen dem Beschwerdeführer und den Söhnen lässt sich nach Massgabe der in der Rechtsprechung anerkannten Grundsätze folglich nicht mit dem Kindeswillen rechtfertigen. Das Verwaltungsgericht verweist daneben auf den (unbestritten) bestehenden heftigen Elternkonflikt. Die Eltern würden sich seit Jahren über das Besuchsrecht streiten und seien nicht in der Lage, die Hilfsangebote der angerufenen Fachstellen zu nutzen und sich gemeinsam auf ein Besuchsrecht zu einigen. Auch wenn sich die Beziehung zwischen dem Vater und den Söhnen vorliegend nicht ausgesprochen gut präsentiert und - zumindest von Seiten der Kinder - eher von einer gewissen Gleichgültigkeit geprägt zu sein scheint, vermag der Elternkonflikt allein die vom Verwaltungsgericht auf unbestimmte Dauer vorgesehene minimale Regelung nach der Rechtsprechung ebenfalls nicht zu rechtfertigen. Zumal der Streit sich nach den vorinstanzlichen Feststellungen vorab um die Ausgestaltung der Kontakte zwischen Vater und Söhnen dreht, dieses Konfliktpotential aber erheblich verringert wird, sobald mit dem Abschluss des vorliegenden Verfahrens eine verbindliche Regelung gefunden ist. Ohnehin sind die Parteien verpflichtet, zum Wohle der Kinder zusammenzuarbeiten (<ref-ruling> E. 2.2.1; Urteil 5A_210/2018 vom 14. Dezember 2018 E. 2.1).
2.6. Zusammenfassend erweist es sich auch mit Blick auf das der Vorinstanz zukommende Ermessen als bundesrechtswidrig, dem Beschwerdeführer unter Hinweis auf den Kindeswillen und den Elternkonflikt ein bloss minimales Kontaktrecht von zwei Nachmittagen im Monat einzuräumen. Folglich ist die Ziffer 1 des angefochtenen Urteils in Gutheissung der Beschwerde aufzuheben. Es ist indes nicht Aufgabe des Bundesgerichts, den persönlichen Verkehr zwischen dem Beschwerdeführer und den Kindern neu zu regeln, zumal sich das Verwaltungsgericht nicht zu den weiteren Umständen des Falls äussert und hierzu auch keine Feststellungen getroffen hat. Die Sache ist daher entsprechend dem Eventualantrag des Beschwerdeführers zum erneuten Entscheid an die Vorinstanz zurückzuweisen (Art. 107 Abs. 2 BGG). Das Verwaltungsgericht wird auch neu über die Kosten des kantonalen Verfahrens zu entscheiden haben, weshalb auch die Ziffern 2 und 3 des angefochtenen Entscheids aufzuheben sind, soweit nicht die (unstrittige) Bewilligung der unentgeltlichen Rechtspflege für das kantonale Beschwerdeverfahren betroffen ist. Auf die vom Beschwerdeführer ebenfalls erhobene Rüge der Verletzung des Anspruchs auf rechtliches Gehör braucht unter diesen Umständen nicht mehr eingegangen zu werden.
3.
Die Rückweisung zum erneuten Entscheid gilt im Hinblick auf die Gerichtskosten und die Parteientschädigung als vollständiges Obsiegen des Beschwerdeführers (<ref-ruling> E. 11.1). Dementsprechend sind die Gerichtskosten der Beschwerdegegnerin aufzuerlegen (Art. 66 Abs. 1 BGG) und hat diese dem Beschwerdeführer die Parteikosten zu ersetzen (Art. 68 Abs. 1 BGG). An der Kostenpflicht der Beschwerdegegnerin ändert nichts, dass diese keine Anträge in der Sache gestellt hat (<ref-ruling> E. 2; Urteil 5A_932/2016 vom 24. Juli 2017 E. 2.2.4 mit zahlreichen Hinweisen). Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege (Art. 64 BGG) wird gegenstandslos und ist abzuschreiben.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen und der Entscheid des Verwaltungsgerichts des Kantons Solothurn vom 10. Januar 2019 wird aufgehoben, soweit nicht die Bewilligung der unentgeltlichen Rechtspflege für das kantonale Beschwerdeverfahren betreffend. Die Sache wird zum erneuten Entscheid an das Verwaltungsgericht zurückgewiesen.
2.
Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege im bundesgerichtlichen Verfahren wird als gegenstandslos geworden abgeschrieben.
3.
Die Gerichtskosten von Fr. 2'000.-- werden der Beschwerdegegnerin auferlegt.
4.
Die Beschwerdegegnerin hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
5.
Dieses Urteil wird den Parteien, der Kindes- und Erwachsenenschutzbehörde Thal-Gäu/Dorneck-Thierstein und dem Verwaltungsgericht des Kantons Solothurn schriftlich mitgeteilt.
Lausanne, 9. Juli 2019
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Herrmann
Der Gerichtsschreiber: Sieber