Sachverhalt:
A.
A. und B. C._ sind Eigentümer und Eigentümerin des mit einem Einfamilienhaus überbauten Grundstücks Nr. 191, Grundbuch Wartau. Dieses grenzt im Osten an das Grundstück Nr. 3186, Grundbuch Wartau, dessen Eigentümerin D._ ist. Die beiden Grundstücke liegen an einem gegen Südosten teilweise steil abfallenden Hang in der Wohnzohne WE und grenzen gegen Süden an die Landwirtschaftszone. Am 18. September 2017 hatte die Baukommission der Gemeinde Wartau den Umbau, die Aufstockung und die Erweiterung des Einfamilienhauses auf dem Grundstück Nr. 191 sowie die Erstellung einer im Abstand von zwei Metern insbesondere entlang der östlichen Grundstücksgrenze verlaufenden Stützmauer mit einer Höhe von 0.65 bis 1.20 Metern und einem darauf verlaufenden 1 Meter hohen Geländer bewilligt.
B.
Am 29. März 2018 reichten A. und B. C._ ein nachträgliches Baugesuch für die Stützmauer ein. Sie hatten diese abweichend von den bewilligten Plänen im Abstand von 0.17 Metern entlang der Grenze zum Grundstück Nr. 3186 und mit einer Höhe von 1.50 bis 1.80 Metern gebaut.
D._ erhob am 17. April 2018 Einsprache gegen das Baugesuch. Der Gemeinderat Wartau wies diese am 3. September 2019 ab und bewilligte die Stützmauer nachträglich unter Auflagen und Bedingungen.
C.
Auf den dagegen von D._ erhobenen Rekurs trat das Baudepartement des Kantons St. Gallen am 6. April 2020 nicht ein, soweit ihre Anträge Fragen der Wiederherstellung für den Fall der Gutheissung des Rekurses und zivilrechtliche Abwehransprüche betrafen. Im Übrigen wies es den Rekurs ab.
D.
Am 17. April 2020 erhob D._ gegen den Rekursentscheid des Baudepartements Beschwerde beim Verwaltungsgericht des Kantons St. Gallen. Dieses hiess die Beschwerde gut, hob den angefochtenen Entscheid auf und wies die Angelegenheit zur Prüfung der Wiederherstellung des rechtmässigen Zustandes an die Gemeinde Wartau zurück.
E.
Dagegen haben A. und B. C._ Beschwerde in öffentlich-rechtlichen Angelegenheiten erhoben. Sie beantragen die vollumfängliche Aufhebung des angefochtenen Entscheids und die Erteilung der nachgesuchten nachträglichen Baubewilligung.
Das Verwaltungsgericht beantragt die Abweisung der Beschwerde unter Verweis auf die Erwägungen im angefochtenen Entscheid. Das Baudepartement beantragt die Gutheissung der Beschwerde. Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde.
F.
Mit Verfügung vom 29. Juni 2021 erkannte das Bundesgericht der Beschwerde die aufschiebende Wirkung zu.

Erwägungen:
1.
Das Bundesgericht prüft seine Zuständigkeit und die Zulässigkeit der Beschwerden von Amtes wegen und mit freier Kognition (Art. 29 Abs. 1 BGG; <ref-ruling> E. 1.1).
2.
Angefochten ist ein kantonal letztinstanzlicher Entscheid, gegen welchen grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten nach Art. 82 ff. BGG offen steht.
3.
3.1. Gemäss Art. 90 und Art. 91 BGG ist die Beschwerde gegen End- und Teilentscheide zulässig. Gegen Vor- und Zwischenentscheide ist die Beschwerde nur nach den Voraussetzungen der Art. 92 und Art. 93 BGG zulässig.
Rechtsprechungsgemäss sind Rückweisungsentscheide, mit denen eine Sache zur neuen Entscheidung an die Vorinstanz zurückgewiesen wird, grundsätzlich Zwischenentscheide, die nur unter den genannten Voraussetzungen beim Bundesgericht angefochten werden können (<ref-ruling> E. 1.4; <ref-ruling> E. 2; <ref-ruling> E. 1.2; <ref-ruling> E. 4.2). Anders verhält es sich nur dann, wenn der unteren Instanz, an welche zurückgewiesen wird, kein Entscheidungsspielraum mehr verbleibt und die Rückweisung nur noch der Umsetzung des oberinstanzlich Angeordneten dient (<ref-ruling> E. 1.4; <ref-ruling> E. 1.2; <ref-ruling> E. 1.2). Rechtsmittelentscheide, mit denen ein kantonal letztinstanzliches Gericht über einen Zwischenentscheid einer unteren Instanz befindet, werden in der Regel ebenfalls als Zwischenentscheide qualifiziert. Mit einem solchen Entscheid wird nicht über ein Rechtsverhältnis endgültig entschieden, sondern nur über einen einzelnen Schritt auf dem Weg zum Endentscheid (<ref-ruling> E. 1.1; <ref-ruling> E. 2.1; <ref-ruling> E. 3.2; Urteil 1C_288/2020 vom 28. April 2021 E. 1.4). Anders verhält es sich lediglich dann, wenn durch den Entscheid der letzten kantonalen Instanz ein Zwischenentscheid der ersten Instanz umgestossen und das Verfahren vor dieser dadurch abgeschlossen wird (BGE <ref-ruling> E. 2.1; <ref-ruling> E. 3.2; Urteil 1C_288/2020 vom 28. April 2021 E. 1.4). Die dargestellte Rechtsprechung entspricht dem gesetzgeberischen Willen, wonach die Eintretensvoraussetzungen von Art. 93 Abs. 1 BGG das Bundesgericht entlasten sollen; dieses soll sich möglichst nur einmal mit einer Sache befassen (<ref-ruling> E. 1.3 mit Hinweisen).
3.2. In einem kürzlich ergangenen Urteil hat das Bundesgericht betreffend den Kanton Appenzell Innerrhoden festgehalten, dass dem nachträglichen Baubewilligungsverfahren nach innerrhodischem Recht das Konzept einer einheitlichen Beurteilung zugrunde liege. Die Baubewilligungsbehörde entscheide nicht nur über die Bewilligungsfähigkeit des Bauvorhabens, sondern auch über die Wiederherstellung des rechtmässigen Zustands. Das Bundesgericht schloss daraus, dass der Rückweisungsentscheid zur Prüfung der Verhältnismässigkeit des Rückbaus das nachträgliche Baubewilligungsverfahren nicht abschliesse und qualifizierte diesen als Zwischenentscheid (vgl. Urteil 1C_288/2020 vom 28. April 2021 E. 2.1 u. 2.2).
3.3. Vorliegend hat das Verwaltungsgericht ebenfalls einen Rückweisungsentscheid getroffen: Es hat die Rechtmässigkeit der umstrittenen Stützmauer verneint und die Angelegenheit zur Prüfung der Wiederherstellung des rechtmässigen Zustandes an die Gemeinde Wartau zurückgewiesen. Auch im Kanton St. Gallen ist das nachträgliche Baubewilligungsverfahren so konzipiert, dass die Baubewilligungsbehörde nicht nur über die Bewilligungsfähigkeit der bereits realisierten Baute, sondern auch über die Wiederherstellung des rechtmässigen Zustands befindet (vgl. Art. 158 und Art. 159 Abs. 1 und 2 des Planungs- und Baugesetzes des Kantons St. Gallen vom 5. Juli 2016 (PBG/SG; sGS 731.1). Somit ist auch der vorliegende Rückweisungsentscheid als Zwischenentscheid zu qualifizieren, der vor Bundesgericht nur nach den Voraussetzungen der Art. 92 bzw. Art. 93 BGG anfechtbar ist.
4.
4.1. Art. 92 BGG betrifft Vor- und Zwischenentscheide über die Zuständigkeit und den Ausstand; diese Bestimmung ist vorliegend offensichtlich nicht anwendbar.
4.2. Nach Art. 93 Abs. 1 BGG ist gegen selbstständig eröffnete Vor- und Zwischenentscheide die Beschwerde zulässig, wenn sie einen nicht wieder gutzumachenden Nachteil bewirken können (lit. a) oder unter der doppelten Voraussetzung, dass die Gutheissung der Beschwerde sofort einen Endentscheid herbeiführen und damit einen bedeutenden Aufwand an Zeit oder Kosten für ein weitläufiges Beweisverfahren ersparen würde (lit. b). Nach konstanter Rechtsprechung haben sodann die Rechtsuchenden im Einzelnen darzulegen, inwiefern die Beschwerdevoraussetzungen nach Art. 93 Abs. 1 BGG erfüllt sind, ansonsten auf die Beschwerde mangels hinreichender Begründung nicht einzutreten ist (<ref-ruling> E. 1.1; <ref-ruling> E. 4; je mit Hinweisen). Ist die Beschwerde gegen einen Zwischenentscheid gemäss Art. 93 Abs. 1 BGG nicht zulässig oder wurde von ihr kein Gebrauch gemacht, bleibt der Zwischenentscheid im Rahmen einer Beschwerde gegen den Endentscheid anfechtbar, soweit er sich auf dessen Inhalt auswirkt (Art. 93 Abs. 3 BGG).
4.3. Die Beschwerdeführenden legen nicht dar, inwiefern ihnen aufgrund des angefochtenen Entscheids ein nicht wieder gutzumachender Nachteil im Sinne von Art. 93 Abs. 1 lit. a BGG entstehen könnte. Ein solcher ist vorliegend auch nicht ersichtlich (vgl. auch Urteil 1C_288/2020 vom 28. April 2021 E. 3.2).
Sie berufen sich des Weiteren auch nicht auf Art. 93 Abs. 1 lit. b BGG. Dazu ist zu bemerken, dass eine Gutheissung der Beschwerde im vorliegenden Fall zwar sofort einen Endentscheid herbeiführen würde. Damit liesse sich jedoch kein bedeutender Aufwand an Zeit oder Kosten ersparen, denn es ist aufgrund der gut dokumentierten Akten nicht ersichtlich, inwieweit im Rahmen des Wiederherstellungsverfahrens noch ein weitläufiges Beweisverfahren nötig wäre. Auch mit Blick auf Art. 93 Abs. 1 lit. b BGG ist die Beschwerde somit unzulässig.
4.4. Den Beschwerdeführenden steht offen, einen allfälligen für sie ungünstigen Endentscheid betreffend die Wiederherstellung des rechtmässigen Zustands anzufechten. Diesfalls können sie das vorliegend angefochtene Urteil des Verwaltungsgerichts zusammen mit dem Endentscheid anfechten, soweit es sich auf dessen Inhalt auswirkt (Art. 93 Abs. 3 BGG).
5.
Nach dem Ausgeführten ist auf die Beschwerde nicht einzutreten. Bei diesem Verfahrensausgang tragen die unterliegenden Beschwerdeführenden die Kosten des bundesgerichtlichen Verfahrens (Art. 66 Abs. 1 BGG). Sie haben der Beschwerdegegnerin zudem eine angemessene Parteientschädigung auszurichten (Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Auf die Beschwerde wird nicht eingetreten.
2.
Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführenden auferlegt.
3.
Die Beschwerdeführenden haben der Beschwerdegegnerin eine Parteientschädigung von Fr. 2'000.-- zu bezahlen.
4.
Dieses Urteil wird den Parteien, der Politischen Gemeinde Wartau, dem Baudepartement des Kantons St. Gallen und dem Verwaltungsgericht des Kantons St. Gallen, Abteilung I, schriftlich mitgeteilt.
Lausanne, 2. November 2021
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Kneubühler
Die Gerichtsschreiberin: Hänni