Sachverhalt:
A.
Die Schweizerin A._ (geb. 1973; Beschwerdeführerin) und der türkische Staatsangehörige B._ (geb. 1991; Beschwerdeführer) ersuchten das Zivilstandsamt der Stadt Schaffhausen am 1. März 2016 um Durchführung eines Ehevorbereitungsverfahrens.
Das Zivilstandsamt lehnte dieses Gesuch mit Verfügung vom 20. Juni 2016 ab.
B.
Hiergegen beschwerten sich A._ und B._ erfolglos erst beim Amt für Justiz und Gemeinden und danach beim Regierungsrat des Kantons Schaffhausen. Die gegen den Regierungsratsbeschluss gerichtete Beschwerde wies das Obergericht des Kantons Schaffhausen mit Entscheid vom 10. August 2018 (eröffnet am 14. August 2018) ab.
C.
Mit Beschwerde vom 14. September 2018 (Datum Poststempel) sind A._ und B._ an das Bundesgericht gelangt. Sie beantragen, das Obergericht sei unter Aufhebung von dessen Entscheid vom 10. August 2018 anzuweisen, auf ihr Heiratsgesuch einzutreten. Eventuell sei die Sache zur Neubeurteilung an das Obergericht zurückzuweisen. Im Falle des Obsiegens seien sie "für die Kosten der Rechtsvertretung vollumfänglich für das bisherige Verfahren zu entschädigen". Ausserdem ersuchen A._ und B._ für das bundesgerichtliche Verfahren um unentgeltliche Rechtspflege.
Das Bundesgericht hat die Akten des kantonalen Verfahrens, indes keine Vernehmlassungen eingeholt.

Erwägungen:
1.
Angefochten ist ein Endentscheid (<ref-law>) einer letzten kantonalen Instanz, die als oberes Gericht (<ref-law>) über ein Gesuch um Einleitung eines Ehevorbereitungsverfahrens (vgl. <ref-law>) und damit eine nicht vermögensrechtliche öffentlich-rechtliche Angelegenheit in unmittelbarem Zusammenhang mit dem Zivilrecht (Art. 72 Abs. 2 Bst. b Ziff. 2 und <ref-law> [im Umkehrschluss]) entschieden hat (vgl. Urteil 5A_337/2016 vom 6. September 2016 E. 2.2). Damit ist die Beschwerde in Zivilsachen das zutreffende Rechtsmittel. Die Beschwerdeführer sind nach <ref-law> zur Beschwerde berechtigt und sie haben diese fristgerecht erhoben (Art. 100 Abs. 1 und Art. 46 Abs. 1 Bst. b BGG). Unter Vorbehalt der nachfolgenden Ausführungen ist auf die Beschwerde einzutreten.
2.
2.1. Mit Beschwerde in Zivilsachen kann die Verletzung von Bundesrecht, einschliesslich des Verfassungsrechts, sowie von Völkerrecht gerügt werden (Art. 95 Bst. a und b BGG). Abgesehen von den hier nicht einschlägigen Fällen des Art. 95 Bst. c-e BGG prüft das Bundesgericht auch die Anwendung von kantonalem Recht einzig daraufhin, ob sie zu einer derartigen Rechtsverletzung führt (namentlich zu einer Verletzung des Willkürverbots [<ref-law>]; <ref-ruling> E. 2.1; <ref-ruling> E. 1.2). Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Dies entbindet die beschwerdeführende Person jedoch nicht davon, die Beschwerde hinreichend zu begründen und in Auseinandersetzung mit den Erwägungen des angefochtenen Entscheids in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>). Eine qualifizierte Rügepflicht gilt für die Rüge der Verletzung von Grundrechten (<ref-law>). Demnach muss in der Beschwerde klar und detailliert anhand der Erwägungen des angefochtenen Entscheids dargelegt werden, inwieweit die angerufenen Rechte verletzt sein sollen. Auf eine nicht hinreichend begründete Beschwerde kann nicht eingetreten werden (<ref-ruling> E. 2.1; <ref-ruling> E. 2.4; <ref-ruling> E. 1.3).
2.2. Was den Sachverhalt angeht, legt das Bundesgericht seinem Urteil die vorinstanzlichen Feststellungen zugrunde (vgl. <ref-law>). Diesbezüglich kann die beschwerdeführende Person nur vorbringen, die vorinstanzlichen 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. Überdies ist darzutun, inwiefern die Behebung der gerügten Mängel für den Ausgang des Verfahrens entscheidend sein kann (vgl. Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG). Es gilt wiederum das strenge Rügeprinzip nach <ref-law>. Das Bundesgericht tritt auf ungenügend substanziierte Rügen und rein appellatorische Kritik am Sachverhalt nicht ein (<ref-ruling> E. 1.3.1, 317 E. 5.4; <ref-ruling> E. 2.3 S. 266).
3.
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 nach dem angefochtenen Entscheid entstanden sind, sind im Verfahren vor Bundesgericht demgegenüber grundsätzlich unbeachtlich (<ref-ruling> E. 3.1.2; <ref-ruling> E. 2.1).
Folglich bleibt es von vornherein unbeachtlich, wenn die Beschwerdeführer auf die seit Ergehen des angefochtenen Entscheids verstrichene Zeit bzw. auf "den Werdegang [ihrer] Beziehung [...] bis zum heutigen Stand" verweisen und hieraus eine Festigung des Ehewillens bzw. eine erhöhte "Glaubwürdigkeit ihrer Zuneigung" ableiten. Nicht weiter zu beachten ist auch die nach dem angefochtenen Entscheid datierende "Absichtserklärung zur Heirat" (Beschwerdebeilage 1). Somit bleiben die auf diese Umstände und Beweismittel gestützten Ausführungen der Beschwerdeführer unbehelflich.
4.
4.1. Gemäss <ref-law> tritt die Zivilstandsbeamtin oder der Zivilstandsbeamte auf ein Eheschliessungsgesuch nicht ein, wenn die Braut oder der Bräutigam offensichtlich keine Lebensgemeinschaft begründen, sondern die Bestimmungen über Zulassung und Aufenthalt von Ausländerinnen und Ausländern umgehen will. Es handelt sich um eine Konkretisierung des Rechtsmissbrauchsverbots von <ref-law>. Die Zivilstandsbeamtin oder der Zivilstandsbeamte darf die Mitwirkung nur verweigern, wenn die zwei folgenden kumulativen Voraussetzungen erfüllt sind. Erstens muss einem der Gesuchsteller jeglicher Wille fehlen, eine eheliche Gemeinschaft zu begründen (vgl. <ref-ruling> E. 3.3.2), wobei unter ehelicher Gemeinschaft eine dauerhafte Lebensgemeinschaft grundsätzlich ausschliesslichen Charakters mit einer geistigen, körperlichen und wirtschaftlichen Komponente verstanden wird. Zweitens muss beabsichtigt sein, mit der Heirat die Bestimmungen über die Zulassung und den Aufenthalt von Ausländern zu umgehen. Beide Voraussetzungen müssen offenkundig erfüllt sein. Der Wille, eine eheliche Gemeinschaft begründen zu wollen, ist ein intimes Element, welches naturgemäss keinem direkten Beweis zugänglich ist. Ein Missbrauch kann nur durch ein Zusammenspiel von Indizien nachgewiesen werden (zum Ganzen: Urteile 5A_337/2016 vom 6. September 2016 E. 5.1.1; 5A_30/2014 vom 15. April 2014 E. 3.3, in: FamPra.ch 2014 S. 693; 5A_225/2011 vom 9. August 2011 E. 5.1.1, in: FamPra.ch 2011 S. 922).
4.2. Solche Indizien können äussere Gegebenheiten sein wie ein grosser Altersunterschied, Schwierigkeiten in der Kommunikation, fehlende Kenntnisse über den anderen Partner oder die Bezahlung einer Entschädigung. Sie können aber auch psychische Vorgänge betreffen, welche den inneren Willen der Gesuchsteller aufzeigen. In beiden Fällen handelt es sich um tatsächliche Feststellungen, welche für das Bundesgericht grundsätzlich verbindlich sind (dazu vorne E. 2.2 [auch zu den Rügeanforderungen]; vgl. Urteil 5A_337/2016 vom 6. September 2016 E. 5.1.2 mit Hinweisen). Rechtsfrage und damit frei zu prüfen ist hingegen, ob die festgestellten Tatsachen (Indizien) darauf schliessen lassen, die Ehe bezwecke die Umgehung ausländerrechtlicher Vorschriften oder sei rechtsmissbräuchlich (Urteil 5A_30/2014 vom 15. April 2014 E. 3.3, in: FamPra.ch 2014 S. 693, mit Hinweis auf <ref-ruling> E. 2.3).
5.
Das Obergericht führte zahlreiche Indizien an, welche seiner Ansicht nach darauf hindeuten, dass der Beschwerdeführer keine Lebensgemeinschaft begründen, sondern die Bestimmungen über Zulassung und Aufenthalt von Ausländern umgehen will:
Als die Beschwerdeführer sich zur Heirat entschlossen und das Gesuch um Ehevorbereitung eingereicht hätten, sei der Aufenthaltsstatus des Beschwerdeführers äusserst prekär gewesen: Der Beschwerdeführer habe im August 2013 um Asyl ersucht. Dieses Gesuch sei abgewiesen und dem Beschwerdeführer eine Ausreisefrist bis zum 5. Februar 2016 angesetzt worden. Da er gegen den Asylentscheid Beschwerde erhoben habe, habe er sich zwar nicht illegal in der Schweiz aufgehalten, als die Beschwerdeführer am 1. März 2016 um Einleitung des Ehevorbereitungsverfahrens ersuchten. Es habe ihm aber die baldige Wegweisung gedroht. Die Beschwerde gegen den Asylentscheid sei denn auch im April 2017 abgewiesen und dem Beschwerdeführer eine neue Ausreisefrist angesetzt worden (vgl. Urteil des Bundesverwaltungsgerichts D-285/2016 vom 27. April 2017).
Die Beschwerdeführer hätten übereinstimmend angegeben, seit dem Jahr 2014 sporadische Kontakte gehabt zu haben und seit Ende 2015 bzw. Anfang 2016 ein Liebespaar zu sein. Sie hätten sich daher erst seit sehr kurzer Zeit nahe gestanden, als sie sich im Januar 2016 verlobten.
Zu beachten sei insbesondere der zeitliche Ablauf: Die Beschwerdeführer seien unbestritten Ende November 2015 noch kein Paar gewesen. Das Asylgesuch des Beschwerdeführers sei am 11. Dezember 2015 abgewiesen worden. Danach hätten sich die Beschwerdeführer innert nur weniger Wochen zur Heirat entschlossen. Der gemeinsame Haushalt sei im Februar 2016 gegründet worden. Diese zeitliche Abfolge sei ein gewichtiges Indiz dafür, dass der Beschwerdeführer durch die Heirat sein Aufenthaltsrecht sichern wolle.
Weiter sei die Beschwerdeführerin 18 Jahre älter als der Beschwerdeführer, womit ein erheblicher Altersunterschied bestehe. Die Beschwerdeführerin leide sodann seit der Studienzeit an psychischen Problemen und ihre beiden Kinder (geboren 2002 und 2004) - zu diesen habe sie Briefkontakt - seien fremdplatziert. Im Zeitpunkt der Befragung durch das Zivilstandsamt habe sie sich in Therapie befunden. Ausserdem habe sie keine Freunde und praktisch keinen Kontakt zu Eltern und Familie. Nach Beobachtungen der Zivilstandsbeamtin sei die Beschwerdeführerin langsam im Denken und brauche viel Zeit, um Fragen zu beantworten. Die mittellose Beschwerdeführerin entspreche daher der Zielgruppe, die für das Eingehen einer Scheinehe angegangen werde.
Die Beschwerdeführer würden sich sodann zwar in ihrer Wohnsituation und im Alltag bereits relativ gut kennen. Hingegen hätten sie nur spärliche Erkenntnisse der jeweiligen Lebenssituation des anderen Partners. Der Beschwerdeführer habe die Beschwerdeführerin seiner Familie noch nicht vorgestellt, weil jene davor Angst habe. Die Beschwerdeführerin sei auch ansonsten kaum über die Familie des Beschwerdeführers informiert und habe sehr viel Zeit für die Beantwortung der Fragen der Zivilstandsbeamtin benötigt.
Aufgrund all dieser Indizien hätten die Vorinstanzen von einer Scheinehe bzw. dem fehlenden Willen des Beschwerdeführers zur Begründung einer dauernden Lebensgemeinschaft ausgehen dürfen. Auch aus dem Umstand, dass die Beschwerdeführer zusammen in einer Einzimmerwohnung lebten und sich um eine positive Gestaltung des Alltags bemühten, könne nichts anderes geschlossen werden. Auf den Bericht der Paartherapeutin der Beschwerdeführer könne sodann nicht abgestellt werden: Die Therapeutin habe unkritisch auf kaum glaubhafte Aussagen des Beschwerdeführers abgestellt (z.B. die Behauptung, es sei Norm in der Familie, ältere Frauen zu heiraten). Ausserdem sei der Erfahrungstatsache Rechnung zu tragen, dass Therapiepersonen mit Blick auf die Vertrauensstellung zu den Patienten eher zu deren Gunsten aussagen würden.
6.
6.1. Die Beschwerdeführer rügen die fehlerhafte Sachverhaltsfeststellung. Das Obergericht sei verpflichtet gewesen, nach dem Entscheid des Regierungsrats entstandene Sachverhaltselemente zu erheben und in seinen Entscheid einfliessen zu lassen. Namentlich hätte es die Beschwerdeführer nochmals befragen müssen. Dem angefochtenen Entscheid lasse sich nicht entnehmen, ob das Obergericht dieser Pflicht nachgekommen sei. Vielmehr stütze die Vorinstanz sich durchgehend auf den "Sachverhaltsstand" im Zeitpunkt der Verfügung des Zivilstandsamts. Indem das Obergericht die auch ohne entsprechenden Antrag vorzunehmende Klärung des Sachverhalts unterlassen habe, habe es die Offizialmaxime verletzt.
Das Verfahren vor dem Obergericht richtet sich nach dem Gesetz des Kantons Schaffhausen vom 20. September 1971 über den Rechtsschutz in Verwaltungssachen (VRG/SH; SHR 172.200; vgl. Art. 35 Abs. 1 Bst. a VRG/SH; vgl. auch <ref-law> i.V.m. Art. 89 Abs. 1 der Zivilstandsverordnung [ZStV; SR 211.112.2]). Dort ist auch die von den Beschwerdeführern angerufene Pflicht zur Sachverhaltsfeststellung von Amtes wegen vorgesehen (Art. 44 Abs. 1 VRG/SH). Die Anwendung des kantonalen Rechts kann das Bundesgericht ebenso wie die Erhebung des Sachverhalts wie ausgeführt auf die Verletzung von Verfassungsrecht hin und nur bei Vorliegen einer hinreichend klaren und detaillierten Rüge prüfen (vorne E. 2). Die Beschwerdeführer machen einerseits die Verletzung des kantonalen Verfahrensrechts geltend und rügen andererseits die mangelhafte Sachverhaltsfeststellung. Inwieweit Verfassungsrecht verletzt sein soll, legen sie nicht dar. Ausserdem begnügen sie sich damit, dem Obergericht in allgemeiner Art und Weise vorzuwerfen, möglicherweise vorgefallene Änderungen im Sachverhalt nicht geklärt zu haben. Welche Änderungen ihrer Ansicht nach eingetreten sind und weshalb das Obergericht einzelne Beweismassnahmen zu Unrecht nicht getroffen haben soll, legen sie nicht dar. Auch der Hinweis, eine neue Parteibefragung sei angezeigt gewesen, bleibt pauschal und die Beschwerdeführer führen nicht aus, inwieweit diese zur weiteren Klärung des Sachverhalts hätte beitragen können. Auf die Beschwerde ist insoweit nicht einzutreten.
6.2. Nach Ansicht der Beschwerdeführer hat das Obergericht den Bericht ihrer Paartherapeutin zu Unrecht als nicht glaubwürdig eingestuft und ihm kein höheres Gewicht beigemessen. Es bleibe unklar, weshalb die Aussagen des Beschwerdeführers, auf welche die Therapeutin abgestellt habe, unglaubwürdig sein sollten. Ausserdem habe das Obergericht den Bericht nicht umfassend gewürdigt. Wesentliche Aspekte - diese würden die Zuneigung und das enge Verhältnis der Brautleute aufzeigen - seien nicht beachtet worden. Das Obergericht dürfe die Meinung der ausgewiesenen Expertin nicht einfach in derart unsubstanziierter Weise disqualifizieren. Das von der Vorinstanz zitierte Urteil 8C_158/2017 vom 22. August 2017 sei sodann nicht einschlägig, da es sich zu einer anderen Sachlage äussere.
Das Obergericht hat dem Bericht der Paartherapeutin nicht nur aus dem von den Beschwerdeführern angesprochenen Grund (unkritische Übernahme gewisser Äusserungen) keine grössere Bedeutung beigemessen. Es führte auch aus, es sei eine Erfahrungstatsache, dass Therapiepersonen aufgrund ihres Vertrauensverhältnisses mit den Patienten dazu neigten, zu deren Gunsten auszusagen (vgl. vorne E. 5 und dazu <ref-ruling> E. 4.5; <ref-ruling> E. 3b/cc). Mit diesem Argument, das für sich allein rechtfertigt, dem fraglichen Bericht kein allzu grosses Gewicht beizumessen, setzen die Beschwerdeführer sich nicht auseinander. Dies wäre indes notwendig gewesen, um der Pflicht zur ausreichenden Begründung der Beschwerde nachzukommen (vgl. BGE <ref-ruling> E. 2.4). Auch in diesem Zusammenhang muss den Beschwerdeführern sodann vorgeworfen werden, dass sie nicht darlegen, inwieweit die Vorinstanz mit ihrem Vorgehen Verfassungsrecht verletzt haben soll. Auf die Beschwerde ist folglich auch insoweit nicht einzutreten.
7.
7.1. In der Sache legen die Beschwerdeführer in einiger Ausführlichkeit dar, dass sie bereits bei Gesuchseinreichung den Willen zur Eheschliessung gehabt hätten und dieser Wille "bis dato unverändert in seiner gesamten Filigranität" bestehe. Gerade die bisher verstrichene Zeit und die Widrigkeiten, welchen die Beschwerdeführer sich ausgesetzt sähen, sprächen "für die Glaubwürdigkeit ihrer Zuneigung und ihres Heiratswillens". Sie würden täglich an ihrer Beziehung arbeiten und diese qualitativ festigen. Dies zeige sich an den Kontakten mit der Familie des jeweiligen Partners, die im Rahmen des Möglichen wesentlich ausgebaut worden seien, am gemeinsamen Kinderwunsch, den gemeinsam geplanten Urlauben und an den Plänen für die Finanzierung der Familie. Der Beschwerdeführer wolle mit der Heirat nicht die ausländerrechtlichen Bestimmungen umgehen. Dieses Ziel hätte der Beschwerdeführer, der ein gutaussehender, heiratsfähiger, intelligenter und sich zunehmend integrierender jungen Mann sei, wesentlich einfacher als durch eine Heirat mit der Beschwerdeführerin erreichen können, wenn es ihm denn nur darum gegangen wäre. Etwa durch Ehelichung einer gleichaltrigen Schweizerin oder einer Landsfrau mit Niederlassungsbewilligung oder Schweizer Bürgerrecht. Zwar spiele die ausländerrechtliche Problematik beim Heiratsentschluss ihre Rolle. Sie sei aber nicht der Grund für die Eheschliessung, die aus Liebe erfolge, sondern allein dafür, gerade jetzt zu heiraten. Der Aufenthaltsstatus des Beschwerdeführers habe daher nur zu einer Vorverschiebung des Heiratszeitpunkts geführt.
Diese Ausführungen bleiben von vornherein insoweit unbeachtlich, als die Beschwerdeführer von dem durch die Vorinstanz bundesrechtskonform festgestellten Sachverhalt abweichen (vorne E. 6) und sie unzulässige echte Noven vorbringen (vorne E. 3). Die Beschwerdeführer äussern sich sodann zwar zu ihrer Motivation für die Heirat. Auch diesbezüglich gehen sie aber in keiner Weise auf den angefochtenen Entscheid und die vom Obergericht angestellten Überlegungen ein. Das Obergericht hat zahlreiche Indizien genannt, welche seiner Ansicht nach dafür sprechen, dass der Beschwerdeführer die Bestimmungen über Zulassung und Aufenthalt von Ausländern umgehen will. Zu diesen Indizien äussern die Beschwerdeführer sich in den vorstehend wiedergegebenen Ausführungen nicht.
7.2. Die Beschwerdeführer machen aber andernorts geltend, entgegen dem Obergericht fehle es an klaren Indizien für ein missbräuchliches Verhalten. Es sei keine ersichtliche Kühle zwischen den Beschwerdeführern oder zumindest seitens des Beschwerdeführers ersichtlich, es sei kein Geld geflossen und es bestehe keine getrennte Schlafsituation. Tatsache sei aber, dass die Beschwerdeführer seit vier Jahren in einer kleinen Einzimmerwohnung lebten und das tägliche Leben zusammen gestalteten. Dies sei positiv zu würdigen. Das Obergericht greife demgegenüber zu "Konstrukten, um dem Bräutigam kühles Kalkül und Verschlagenheit zu unterstellen". Die Beschwerdegegnerin werde gleichsam als unzurechnungsfähig dargestellt. Da eine Umgehung der ausländerrechtlichen Bestimmungen leichter möglich wäre als durch Heirat der Beschwerdeführerin spreche sodann auch der Altersunterschied eher für als gegen einen aufrichtigen Heiratswillen des Beschwerdeführers.
Soweit sie sich auch insoweit nicht auf unzulässige Noven berufen, stellen die Beschwerdeführer mit diesen Ausführungen einzig ihre Sicht der Dinge dar und werfen dem Obergericht pauschal vor, mit unzulässigen Mitteln ihre Ehe verhindern zu wollen. Die nötige Auseinandersetzung mit dem angefochtenen Entscheid findet auch insoweit nicht statt. Den Beschwerdeführern hilft es insbesondere nicht weiter, wenn sie auf das Fehlen einzelner Indizien verweisen, welche typischerweise auf einen Missbrauch hinweisen (zu diesen vorne E. 4.2). Allein weil einzelne dieser Anhaltspunkte nicht vorliegen, bedeutet dies noch nicht, dass keine anderen bestehen.
7.3. Die Beschwerdeführer werfen dem Obergericht weiter vor, nicht auf ihr Vorbringen eingegangen zu sein, vor Bundesverwaltungsgericht sei ein neues Asylverfahren - ein zweites Revisionsverfahren mit neuen Beweismitteln - hängig. Dem Beschwerdeführer stehe damit ein prozessuales Aufenthaltsrecht zu, was eines der vom Obergericht monierten Indizien entkräfte. Die Vorinstanz habe es willkürlich unterlassen, diesen Punkt weiter abzuklären.
Mit diesem Vorbringen verkennen die Beschwerdeführer den angefochtenen Entscheid: Das Obergericht hat dem Beschwerdeführer nicht vorgeworfen, über keinen Aufenthaltsstatus in der Schweiz zu verfügen. Vielmehr führte es aus, sein Status sei aufgrund des abgewiesenen Asylgesuches und der deswegen drohenden Wegweisung äusserst prekär gewesen, als das streitbetroffene Gesuch gestellt worden sei (vgl. vorne E. 5). An dieser Einschätzung ändert sich selbst dann nichts, wenn der Beschwerdeführer ein zweites Revisionsgesuch beim Bundesverwaltungsgericht eingereicht haben sollte. Etwas anderes würde gegebenenfalls gelten, wenn der Beschwerdeführer tatsächlich Asyl erhalten hätte, was aber nicht geltend gemacht wird. Das Obergericht trifft damit keinen Vorwurf, wenn es einem entsprechenden Vorbringen der Beschwerdeführer - ein solches ist zwar behauptet, aber nicht belegt - nicht weiter nachgegangen sein sollte (vgl. <ref-ruling> E. 9.3.2; <ref-ruling> E. 6.3.1).
7.4. Die Beschwerdeführer verweisen sodann darauf, dass nach der Rechtsprechung die Absicht, sich mittels einer Heirat ein Aufenthaltsrecht zu sichern, nur dann "für eine Scheinehe massgebend sein kann", wenn sie das einzige Heiratsmotiv darstellt. Die Trauung dürfe nur verweigert werden, wenn die "Scheinehemotivation offensichtlich" sei und somit ins Auge springe. Dies sei vorliegend nicht der Fall, weshalb die Trauung zu bewilligen sei. Die Behörden hätten denn auch keine Strafanzeige wegen Verdachts auf das Eingehen einer Scheinehe erstattet.
Unbesehen darum, ob diese Ausführungen zur Rechtslage zutreffen, vermögen die Beschwerdeführer hieraus nichts für sich abzuleiten: Mit diesen allgemeinen rechtlichen Hinweisen zeigen sie nicht auf, dass der angefochtene Entscheid rechtsfehlerhaft ist. Im Zusammenhang mit der Schlussfolgerung, wonach kein offensichtlicher Missbrauch vorliege, stellen sie sodann wiederum allein ihre Würdigung der Sachlage derjenigen des Obergerichts gegenüber. Zuletzt hilft den Beschwerdeführern ihr Vorbringen nicht weiter, die zuständigen Behörden hätten keine Strafanzeige erstattet, was viele Gründe haben kann.
7.5. Auch mit Blick auf die Rüge der Verletzung von <ref-law> erweist sich die Beschwerde damit als unbegründet, soweit darauf einzutreten ist.
Soweit die Beschwerdeführer mit dem nicht weiter erläuterten Hinweis, das Obergericht habe sich nicht mit einer Rüge ihres Rechtsvertreters auseinandergesetzt, eine Verletzung des Anspruchs auf rechtliches Gehör (<ref-law>) geltend machen sollten, erweist sich auch dieses Vorbringen als ungenügend begründet (vorne E. 2.1).
8.
Soweit auf sie einzutreten ist, erweist sich die Beschwerde nach dem Ausgeführten insgesamt als unbegründet und ist abzuweisen. Bei diesem Ausgang des Verfahrens hätten die Beschwerdeführer die Gerichtskosten zu tragen. Mit Blick auf ihre wirtschaftlichen Verhältnisse ist auf die Kostenerhebung allerdings zu verzichten (<ref-law>). Dem Kanton Schaffhausen ist keine Parteientschädigung geschuldet (Art. 68 Abs. 1 und 3 BGG). Das Gesuch der Beschwerdeführer um unentgeltliche Rechtspflege (<ref-law>) wird damit gegenstandslos und ist abzuschreiben.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf eingetreten wird.
2.
Das Gesuch der Beschwerdeführer um unentgeltliche Rechtspflege wird als gegenstandslos geworden abgeschrieben.
3.
Es werden keine Gerichtskosten erhoben.
4.
Parteientschädigung wird keine gesprochen.
5.
Dieses Urteil wird den Verfahrensbeteiligten sowie dem Regierungsrat und dem Obergericht des Kantons Schaffhausen schriftlich mitgeteilt.
Lausanne, 28. Dezember 2018
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: von Werdt
Der Gerichtsschreiber: Sieber