Sachverhalt:
A.
Das Interkantonale Labor in Schaffhausen erteilte der G._ AG am 17. Dezember 2015 eine bis zum 31. Dezember 2017 befristete Bewilligung, auf Parzelle Nr. 1400 in der Gemeinde Thayngen eine Anlage zur Zwischenlagerung von Abfällen zu betreiben.
Am 6. Dezember 2017 bewilligte das Interkantonale Labor der G._ AG, auf besagtem Grundstück eine Abfallanlage zur Sortierung und Lagerung von Altmetall und Altholz zu betreiben, befristet bis zum 31. Dezember 2022. Auf die dagegen eingereichten "Gesuche" von A._, C._, D._ und des Vereins F._ trat es nicht ein und die "Gesuche" von B._ und E._ wies es ab, soweit es darauf eintrat.
B.
A._, B._, C._, D._, E._ und der Verein F._ (nachfolgend: die Rekurrenten) fochten diese Verfügung beim Regierungsrat des Kantons Schaffhausen an. Sie beantragten unter anderem die Aufhebung der Verfügung und die Beauftragung des Baudepartements, in Zusammenarbeit mit der kommunalen Baupolizeibehörde die nötigen Anordnungen zur Wiederherstellung eines baurechtskonformen Zustands zu erlassen. In verfahrensrechtlicher Hinsicht ersuchten sie insbesondere darum, dem Rekurs die aufschiebende Wirkung zu belassen.
Auf Antrag der G._ AG entzog der Regierungsrat des Kantons Schaffhausen dem Rekurs mit Beschluss vom 31. Januar 2018 superprovisorisch die aufschiebende Wirkung. Die Rekurrenten ersuchten darauf um Wiederherstellung der aufschiebenden Wirkung und Anordnung zusätzlicher vorsorglicher Massnahmen. Eventualiter sei der G._ AG eine angemessene Frist zur Einreichung eines Baugesuchs anzusetzen und ein Betriebsverbot bzw. eine wesentliche Einschränkung des Lagerbetriebs anzuordnen; subeventualiter sei in einem Zwischenverfahren über die Baubewilligungspflicht zu entscheiden. Der Regierungsrat beschloss am 27. März 2018, die angeordnete superprovisorische Massnahme in eine vorsorgliche Massnahme zu überführen und die aufschiebende Wirkung des Rekurses zu entziehen.
C.
Dagegen erhoben die Rekurrenten Verwaltungsgerichtsbeschwerde an das Obergericht des Kantons Schaffhausen, wobei sie neben der Aufhebung des regierungsrätlichen Beschlusses und der Wiederherstellung der aufschiebenden Wirkung eventualiter beantragten, dass für den Betrieb des Zwischenlagers einschränkende vorsorgliche Massnahmen anzuordnen seien und der Regierungsrat zu verpflichten sei, geeignete Aufsichtsmassnahmen zur Herstellung des baurechtskonformen Zustands zu ergreifen. Das Obergericht wies die Beschwerde mit Entscheid vom 18. Dezember 2018 ab.
D.
Gegen diesen Entscheid gelangen die Rekurrenten mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 18. Januar 2019 an das Bundesgericht. Sie beantragen in erster Linie die Aufhebung des obergerichtlichen Entscheids und des Entscheids des Regierungsrats sowie die Wiederherstellung der aufschiebenden Wirkung ihres Rekurses im regierungsrätlichen Verfahren. Ausserdem sei das kantonale Baudepartement bzw. das kantonale Bauinspektorat / Planungs- und Naturschutzamt als kantonale Baupolizeibehörde (eventuell der Gemeinderat Thayngen als kommunale Baupolizeibehörde) anzuweisen, für den bestehenden Zwischenlagerbetrieb umgehend ein baurechtliches Wiederherstellungsverfahren bzw. ein nachträgliches Baubewilligungsverfahren einzuleiten und die in diesem Zusammenhang erforderlichen Massnahmen zu treffen.
Das Obergericht und das Interkantonale Labor verzichten unter Verweis auf den Entscheid bzw. die Verfügung und die Eingaben bei der Vorinstanz auf eine Vernehmlassung. Der Regierungsrat beantragt die vollumfängliche Abweisung der Beschwerde, verweist auf seinen Beschluss und verzichtet auf eine weitergehende Vernehmlassung. Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Beschwerdeführer halten in ihrer Stellungnahme an ihrer Beschwerde fest.

Erwägungen:
1.
Angefochten ist ein kantonal letztinstanzlicher Entscheid über eine Angelegenheit des öffentlichen Rechts. Dagegen steht grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht offen (Art. 82 lit. a, Art. 86 Abs. 1 lit. d und Abs. 2 BGG).
1.1. Beim angefochtenen Entscheid, mit welchem der Entzug der aufschiebenden Wirkung des Rekurses bestätigt wurde, handelt es sich um einen selbständig eröffneten Zwischenentscheid. Ein solcher ist unter anderem anfechtbar, wenn er einen nicht wieder gutzumachenden Nachteil bewirken kann (<ref-law>). Dies ist vorliegend zu bejahen, da die Beschwerdegegnerin bei Fehlen der aufschiebenden Wirkung die strittige Anlage weiterbetreiben kann und die Beschwerdeführer den damit verbundenen Lärmimmissionen weiterhin ausgesetzt sind. Dieser Nachteil liesse sich bei einer Gutheissung der Beschwerde in der Hauptsache nicht rückgängig machen.
Ob der angefochtene Entscheid teilweise als Endentscheid zu qualifizieren ist, wie dies die Beschwerdeführer geltend machen (vgl. unten E. 4), kann mit Blick auf die Eintretensfrage offen bleiben.
1.2. Gemäss Verfügung des Interkantonalen Labors vom 6. Dezember 2017 ist die Intensivierung des Lastwagenverkehrs um mindestens ein Vierfaches gegenüber der Bewilligung vom 17. Dezember 2015 zumindest für einen Teil der Beschwerdeführer wahrnehmbar. Die betreffenden Personen sind damit gemäss bundesgerichtlicher Rechtsprechung grundsätzlich zur Beschwerde legitimiert (<ref-ruling>). Ob das Beschwerderecht sämtlichen Beschwerdeführern zukommt, kann offen gelassen werden.
1.3. Bei einem Zwischenentscheid über die aufschiebende Wirkung handelt es sich um eine vorsorgliche Massnahme gemäss <ref-law> (<ref-ruling> E. 1.5 S. 196 f.). Mit der Beschwerde kann somit nur die Verletzung von verfassungsmässigen Rechten gerügt werden. Insoweit gelten die qualifizierten Begründungsanforderungen nach <ref-law>. Die Beschwerdeführer müssen darlegen, welche verfassungsmässigen Rechte bzw. welche Rechtssätze der angefochtene Entscheid inwiefern verletzen soll. Das Bundesgericht prüft nur klar und detailliert erhobene und, soweit möglich, belegte Rügen (<ref-ruling> E. 3.2 S. 579; <ref-ruling> E. 2.1 S. 372; <ref-ruling> E. 1.3 S. 41; je mit Hinweisen). Diesen Anforderungen genügt die Beschwerdeschrift nur teilweise. Soweit die Beschwerdeführer Ausführungen in der Sache machen, namentlich zur Baubewilligungspflicht gemäss Art. 22 RPG (SR 700), und in diesem Zusammenhang Beweisanträge stellen, ist darauf nicht einzutreten.
1.4. Mit diesem Vorbehalt ist auf die Beschwerde einzutreten.
2.
Zunächst rügen die Beschwerdeführer eine Verletzung des rechtlichen Gehörs (<ref-law>) und eine willkürliche Sachverhaltsfeststellung (<ref-law>).
2.1. Sie bringen vor, dass die Vorinstanz hinsichtlich der wirtschaftlichen Auswirkungen des Entzugs der aufschiebenden Wirkung einseitig und ohne weitere Abklärungen auf die nicht substanziierten und nicht belegten Angaben der Beschwerdegegnerin abgestellt und die von ihnen in diesem Zusammenhang im Verfahren vor dem Regierungsrat erhobenen Einwände nicht berücksichtigt habe.
Das Obergericht erwog, dass die Gewährung der aufschiebenden Wirkung für die Beschwerdegegnerin unbestritten erhebliche wirtschaftliche Folgen hätte, da diese ihren Betrieb auf dem betreffenden Areal einstellen müsste. Auch wenn bestimmte Angaben durch die Beschwerdegegnerin nicht hinreichend substanziiert belegt worden seien, hätten die Beschwerdeführer diese nicht bestritten und erscheine es immerhin glaubhaft, dass mit der Gewährung der aufschiebenden Wirkung eine erhebliche Ertragseinbusse sowie die Gefährdung von vier bis sechs Mitarbeiterstellen und von langfristigen Kundenbeziehungen verbunden wären.
Dabei kann, entgegen der Auffassung der Beschwerdeführer, keine Rede von einer einseitigen Würdigung sein. Ebensowenig lassen diese Erwägungen Willkür oder eine Verletzung des rechtlichen Gehörs erkennen, haben die Beschwerdeführer doch vor Obergericht selbst eingeräumt, dass die Wiederherstellung der aufschiebenden Wirkung gewichtige wirtschaftliche Nachteile für die Beschwerdegegnerin zur Folge hätte (Verwaltungsgerichtsbeschwerde [ergänzende Beschwerdebegründung] S. 9 Rz. 7).
2.2. Weiter werfen die Beschwerdeführer dem Obergericht vor, ohne jegliche Auseinandersetzung mit den von ihnen angeführten Rekursgründen eine Gefahr für die Umwelt und die Verkehrssicherheit durch den Betrieb der umstrittenen Anlage und die Zulieferung über eine verkehrsberuhigte Quartierstrasse ausgeschlossen zu haben.
Die Vorinstanz legte indessen dar, weshalb die für die Gewährung der aufschiebenden Wirkung sprechenden umweltschutzrechtlichen Interessen vorliegend nicht entscheidend ins Gewicht fielen und eine summarische Prüfung keine relevante Gefahr für die Umwelt ergebe. Es ist nicht ersichtlich und wird von den Beschwerdeführern auch nicht geltend gemacht, dass die Ausführungen der Vorinstanz inhaltlich offensichtlich unzutreffend seien. Das vorinstanzliche Vorgehen ist aus verfassungsrechtlicher Sicht nicht zu beanstanden.
2.3. Schliesslich machen die Beschwerdeführer geltend, es sei unzutreffend und aktenwidrig, dass der Betrieb nun schon seit über zwei Jahren bestehe und sie sich gegen die ursprüngliche Betriebsbewilligung nicht gewehrt hätten.
Vorliegend hielt die Vorinstanz fest, dass die im Jahr 2015 erteilte Bewilligung unangefochten geblieben und während zwei Jahren von ihr Gebrauch gemacht worden sei, woran das Vorbringen der Beschwerdeführer, sie seien in das Verfahren nicht einbezogen worden, nichts ändere.
Inwiefern diese Feststellungen willkürlich sein sollten, ist nicht ersichtlich. Hinzu kommt, dass mit Blick auf die Gewährung oder Verweigerung der aufschiebenden Wirkung nicht entscheidend ist, ob und inwieweit sich die Beschwerdeführer gegen die erste Bewilligung gewehrt haben, womit eine willkürliche Sachverhaltsfeststellung vorliegend auch mangels Entscheidrelevanz zu verneinen ist.
3.
Die Beschwerdeführer machen sodann eine willkürliche Rechtsanwendung durch die Vorinstanz geltend (<ref-law>).
Sie bringen in erster Linie vor, dass die Erteilung einer abfallrechtlichen Betriebsbewilligung das Bestehen einer Baubewilligung voraussetze. Da eine solche vorliegend fehle, sei für den gegen die Betriebsbewilligung vom 6. Dezember 2017 erhobenen Rekurs eine klare Hauptsachenprognose hinsichtlich seiner voraussichtlichen Gutheissung gegeben, was den Entzug der aufschiebenden Wirkung in Anwendung von Art. 23 des Gesetzes des Kantons Schaffhausen vom 20. September 1971 über den Rechtsschutz in Verwaltungssachen (Verwaltungsrechtspflegegesetz, VRG; SHR 172.200) ausschliesse. Die von der Vorinstanz in diesem Zusammenhang vorgenommene Güter- und Interessenabwägung leide insoweit an einem gravierenden Rechtsfehler und erscheine daher willkürlich.
Zwar kann die Hauptsachenprognose beim Entscheid über die Gewährung oder den Entzug der aufschiebenden Wirkung berücksichtigt werden, wenn sie eindeutig ist; jedoch drängt sich bei tatsächlichen oder rechtlichen Unklarheiten Zurückhaltung auf, weil in diesem Fall die erforderlichen Entscheidgrundlagen im Hauptverfahren erst noch beschafft werden müssen (<ref-ruling> E. 2.2 S. 155 mit Hinweisen). Vorliegend setzte sich die Vorinstanz mit dem mutmasslichen Ausgang des Hauptverfahrens auseinander und führte dabei insbesondere aus, dass sich bei summarischer Betrachtung in Bezug auf die Frage des Bestehens einer Baubewilligungspflicht aufgrund erheblicher Differenzen zwischen den Ausführungen der Verfahrensbeteiligten keine eindeutige Entscheidprognose ergebe. Die diesbezüglich relevante Sach- und Rechtslage lasse sich nicht im Rahmen einer ersten Prüfung durch das Obergericht klären. Es ist daher nicht zu beanstanden, wenn die Vorinstanz bei ihrem Entscheid nicht auf eine Hauptsachenprognose abstellte, insbesondere kann darin keine willkürliche Rechtsanwendung erblickt werden.
4.
Die Beschwerdeführer monieren schliesslich, dass im kantonalen Verfahren alle zuständigen Behörden, trotz ausdrücklicher und formeller Aufforderung zur Einleitung eines baurechtlichen Wiederherstellungsverfahrens bzw. eines nachträglichen Baubewilligungsverfahrens, untätig geblieben seien bzw. ein Einschreiten abgelehnt hätten. Damit liege eine sich über alle Instanzen erstreckende behördliche Untätigkeit und Rechtsverweigerung im Sinne von <ref-law> vor. Schliesslich habe die Vorinstanz auch über den Antrag, dass der Regierungsrat zu verpflichten sei, aufsichtsrechtliche Massnahmen zur Herstellung des baurechtskonformen Zustands zu ergreifen, nicht entschieden, was eine Rechtsverweigerung und überdies eine Verletzung der Rechtsweggarantie darstelle (<ref-law>).
4.1. Das Obergericht hielt - insbesondere mit Rücksicht auf die unsichere Hauptsachenprognose (vgl. oben E. 3) - fest, auf die Anordnung vorsorglicher Massnahmen sei zu verzichten (angefochtener Entscheid E. 4.7). Insoweit erweist sich der Vorwurf der Rechtsverweigerung als unbegründet, wurde der entsprechende Antrag der Beschwerdeführer doch behandelt.
Diesbezüglich ist auch keine Willkür erkennbar: Die Frage der Baubewilligungspflicht wird - wie dies die Beschwerdeführer im Rahmen ihrer Rekursschrift an den Regierungsrat betonen und aus dem Beschluss des Regierungsrats vom 27. März 2018 hervorgeht - Gegenstand des Hauptverfahrens sein (vgl. insbesondere Rekursantrag Ziff. 4 und verfahrensrechtlicher Antrag Ziff. 2). Wäre der Regierungsrat oder das Obergericht bereits im Rahmen des vorliegenden Verfahrens betreffend den Entzug der aufschiebenden Wirkung den von den Beschwerdeführern gestellten Anträgen gefolgt und hätte die zuständige Behörde zur Einleitung eines baurechtlichen Wiederherstellungsverfahrens bzw. eines nachträglichen Baubewilligungsverfahrens verpflichtet, wäre damit der Entscheid in der Hauptsache unzulässigerweise vorweggenommen bzw. präjudiziert worden. Im Unterbleiben einer entsprechenden Anweisung durch die Vorinstanzen kann demnach keine Verletzung verfassungsmässiger Rechte erblickt werden.
Aus demselben Grund besteht auch für das Bundesgericht keine Veranlassung, der zuständigen Behörde eine entsprechende Anweisung zu erteilen.
4.2. Nicht eingetreten ist das Obergericht indessen auf den Antrag der Beschwerdeführer hinsichtlich der Anordnung aufsichtsrechtlicher Massnahmen (angefochtener Entscheid E. 5), weil auf diese grundsätzlich - ausser im Fall der Rechtsverzögerung oder -verweigerung - kein Rechtsanspruch bestehe und insoweit die Verwaltungsgerichtsbeschwerde nicht offen stehe.
Dagegen bringen die Beschwerdeführer vor, sie hätten zumindest sinngemäss Rechtsverzögerung bzw. -verweigerung in Bezug auf die Einleitung eines baurechtlichen Wiederherstellungsverfahrens bzw. eines nachträglichen Baubewilligungsverfahrens geltend gemacht, weshalb die Vorinstanz aufsichtsrechtliche Massnahmen hätte anordnen müssen.
Mit ihren Vorbringen vermögen die Beschwerdeführer nicht darzulegen, dass die vorinstanzlichen Ausführungen offensichtlich unzutreffend wären und sie eine Rechtsverweigerungs- oder Rechtsverzögerungsbeschwerde erhoben hätten. Gegenstand des Rekursverfahrens ist sodann nicht die Untätigkeit oder Verzögerung des Verfahrens durch die erstinstanzliche Behörde, so dass in diesem Zusammenhang aufsichtsrechtliche Massnahmen angezeigt wären. Vielmehr ist die Erteilung der Betriebsbewilligung Gegenstand des aktuell - soweit ersichtlich - beim Regierungsrat hängigen Hauptverfahrens. Zwar haben die Beschwerdeführer im Rekursverfahren den Antrag gestellt, es seien die nötigen Anordnungen zur Wiederherstellung eines baurechtskonformen Zustands zu erlassen. Über diesen Antrag muss der Regierungsrat jedoch im Hauptverfahren entscheiden und nicht im Rahmen des Verfahrens betreffend den Entzug der aufschiebenden Wirkung. In Bezug auf das Hauptverfahren haben die Beschwerdeführer keine unzulässige Rechtsverzögerung oder -verweigerung gerügt.
5.
Nach dem Ausgeführten ist die Beschwerde abzuweisen, soweit darauf eingetreten werden kann.
Bei diesem Ausgang des Verfahrens sind die Gerichtskosten den unterliegenden Beschwerdeführern unter solidarischer Haftung aufzuerlegen (Art. 66 Abs. 1 und 5 BGG). Überdies haben sie die anwaltlich vertretene Beschwerdegegnerin für das bundesgerichtliche Verfahren, ebenfalls unter Solidarhaft, angemessen zu entschädigen (vgl. Art. 68 Abs. 1, 2 und 4 BGG). Die in ihrem amtlichen Wirkungskreis obsiegenden Behörden haben keinen Anspruch auf Parteientschädigung (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 4'000.-- werden den Beschwerdeführern unter solidarischer Haftung auferlegt.
3.
Die Beschwerdeführer haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren unter solidarischer Haftung mit insgesamt Fr. 3'500.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien, dem Interkantonalen Labor, dem Gemeinderat Thayngen, dem Bauinspektorat / Planungs- und Naturschutzamt des Kantons Schaffhausen, dem Regierungsrat des Kantons Schaffhausen und dem Obergericht des Kantons Schaffhausen schriftlich mitgeteilt.
Lausanne, 3. Mai 2019
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Chaix
Die Gerichtsschreiberin: Dambeck