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.