Sachverhalt:
A.
A.A._ und B.A._ sind Eigentümer der Parzelle Nr. xxx, Grundbuch U._. Die Parzelle liegt in der Wohnzone B._. Auf dem Grundstück befinden sich unter anderem ein Einfamilienhaus und ein Schwimmbad mit Stützmauer.
Auf eine entsprechende Aufforderung der Baukommission U._ hin ersuchten A.A._ und B.A._ im März 2018 um eine nachträgliche Baubewilligung für eine Gartengestaltung mit einer Terrasse auf Stützen, eine Sichtschutzmauer und einen Pavillon. Mit kostenpflichtigem Entscheid vom 5. November 2018 verweigerte der Gemeinderat U._ diese Bewilligung. Zudem verpflichtete er die Gesuchsteller, die Terrasse inkl. Stützen sowie Pavillon mindestens im Grenzabstandsbereich zurückzubauen und die Sichtschutzmauer um 1.41 m zu kürzen bzw. in der Höhe auf maximal 1.20 m herabzusetzen.
B.
Den dagegen erhobenen Rekurs von A.A._ und B.A._ hiess das Baudepartement des Kantons St. Gallen mit Entscheid vom 21. April 2020 teilweise gut. Das Departement hob den Entscheid des Gemeinderates vom 5. November 2018 auf, soweit er die Wiederherstellung des rechtmässigen Zustandes sowie die A.A._ und B.A._ auferlegten Gebühren betraf. Ferner wies es die Angelegenheit in diesen Punkten zu neuem Entscheid im Sinne der Erwägungen an den Gemeinderat U._ zurück. Im Übrigen wurde der Rekurs abgewiesen.
C.
Auf eine gegen den Entscheid des Baudepartements erhobene Beschwerde trat das Verwaltungsgericht des Kantons St. Gallen mit Entscheid vom 25. Mai 2021 insoweit nicht ein, als sie die Gebühren im Verfahren vor dem Gemeinderat U._ betraf. Im Übrigen wies das Verwaltungsgericht die Beschwerde ab.
D.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 22. Juni 2021 beantragen A.A._ und B.A._, den Entscheid des Verwaltungsgerichts vom 25. Mai 2021 aufzuheben und die Sache zu neuer Entscheidung an dieses Gericht zurückzuweisen. In verfahrensrechtlicher Hinsicht ersuchen sie um aufschiebende Wirkung der Beschwerde.
Das Baudepartement schliesst auf Abweisung der Beschwerde. Der Gemeinderat und das Verwaltungsgericht beantragen, die Beschwerde abzuweisen, soweit darauf einzutreten sei.
Mit Präsidialverfügung vom 12. Juli 2021 sprach das Bundesgericht der Beschwerde antragsgemäss aufschiebende Wirkung zu.

Erwägungen:
1.
1.1. Das Bundesgericht prüft seine Zuständigkeit und die Zulässigkeit der Beschwerde von Amtes wegen und mit freier Kognition (<ref-law>; <ref-ruling> E. 1.1; Urteil 1C_288/2020 vom 28. April 2021 E. 1.1).
1.2. Beim angefochtenen Entscheid handelt es sich um einen kantonal letztinstanzlichen Entscheid in einer Bausache, gegen den grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten nach <ref-law> offensteht (<ref-ruling> E. 1.1; Urteil 1C_288/2020 vom 28. April 2021 E. 1.2). Die Beschwerdeführer haben am vorinstanzlichen Verfahren teilgenommen und sind als Baugesuchsteller grundsätzlich berechtigt, Beschwerde beim Bundesgericht zu erheben (<ref-law>). Näher zu prüfen ist, ob es sich beim angefochtenen Urteil um einen anfechtbaren Entscheid im Sinne von <ref-law> handelt (zum Ganzen: Urteil 1C_288/2020 vom 28. April 2021 E. 1.2).
1.3. Der Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht unterliegen Endentscheide; diese schliessen das Verfahren ab (<ref-law>). Wird über eines oder einige von mehreren Rechtsbegehren entschieden, so liegt gemäss <ref-law> ein Teilentscheid vor, wenn diese Begehren unabhängig von den anderen beurteilt werden können. Ein Teilentscheid bildet eine Variante eines Endentscheids (vgl. <ref-ruling> E. 2.2; <ref-ruling> E. 1.1). Gegen Vor- und Zwischenentscheide ist die Beschwerde abgesehen von vorliegend nicht relevanten Ausnahmen (<ref-law>) nur dann zulässig, wenn diese einen nicht wieder gutzumachenden Nachteil bewirken können (<ref-law>) oder wenn 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 (<ref-law>). Für die verfahrensrechtliche Qualifizierung eines angefochtenen Erkenntnisses unter dem Gesichtspunkt von <ref-law> ist nicht dessen formelle Bezeichnung entscheidend, sondern sein materieller Gehalt (<ref-ruling> E. 1.1.2; <ref-ruling> E. 1.3.1; zum Ganzen: Urteil 1C_288/2020 vom 28. April 2021 E. 1.3).
1.4. 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 bloss noch der Umsetzung des oberinstanzlich Angeordneten dient (<ref-ruling> E. 1.4; <ref-ruling> E. 1.2; <ref-ruling> E. 1.2; zum Ganzen: Urteil 1C_288/2020 vom 28. April 2021 E. 1.4).
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; vgl. auch FELIX UHLMANN, in: Basler Kommentar, Bundesgerichtsgesetz, 3. Aufl. 2018, N. 10 zu <ref-law>). 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; vgl. auch Botschaft vom 28. Februar 2001 zur Totalrevision der Bundesrechtspflege, BBl 2001 4202 Ziff. 4.1.4.1 S. 4332). Die dargestellte Rechtsprechung entspricht dem gesetzgeberischen Willen, wonach die Eintretensvoraussetzungen von <ref-law> das Bundesgericht entlasten sollen; dieses soll sich möglichst nur einmal mit einer Sache befassen (<ref-ruling> E. 1.3; <ref-ruling> E. 1.3.2; <ref-ruling> E. 2.1; zum Ganzen: Urteil 1C_288/2020 vom 28. April 2021 E. 1.4).
2.
2.1. Vorliegend hat das Verwaltungsgericht keinen Rückweisungsentscheid gefällt. Indessen hat das Baudepartement mit seinem Entscheid vom 21. April 2020 den Rekurs der Beschwerdeführer insoweit gutgeheissen, als es die Sache zur neuen Beurteilung der Wiederherstellung des rechtmässigen Zustandes (und zur Neubemessung der Gebühren) an den Gemeinderat zurückgewiesen hat. Soweit ersichtlich, hat der Gemeinderat bisher noch nicht über die Wiederherstellung entschieden. Gestützt auf die genannten Grundsätze ist deshalb zu prüfen, ob das angefochtene Urteil aufgrund des Entscheids des Baudepartements als Zwischenentscheid gemäss <ref-law> zu qualifizieren ist.
2.2. Gemäss dem Wortlaut von Art. 159 Abs. 1 des Planungs- und Baugesetzes des Kantons St. Gallen vom 5. Juli 2016 (PBG/SG; sGS 731.1) wird, wenn durch die Errichtung von Bauten und Anlagen ohne Bewilligung oder auf andere Weise ein unrechtmässiger Zustand geschaffen wird, insbesondere eine Frist zur Einreichung eines nachträglichen Baugesuchs angesetzt (lit. c) und die Wiederherstellung des rechtmässigen Zustandes verfügt (lit. d). Wie aus dieser im angefochtenen Entscheid herangezogenen Regelung ersichtlich ist, liegt dem nachträglichen Baubewilligungsverfahren nach kantonalem Recht das Konzept einer einheitlichen Beurteilung zugrunde. Die politische Gemeinde entscheidet somit nicht nur über die Bewilligungsfähigkeit des Bauvorhabens, sondern gleichzeitig auch über die Wiederherstellung des rechtmässigen Zustandes (vgl. zur Zuständigkeit auch Art. 158 PBG/SG). Das nachträgliche Baubewilligungsverfahren im Kanton St. Gallen ist mit anderen Worten nicht so gegliedert, dass in einem ersten Verfahrensschritt zunächst die Bewilligungsfähigkeit einer Baute oder Anlage abschliessend beurteilt wird und erst nach dem Vorliegen eines rechtskräftigen Bauentscheids über die Wiederherstellung des rechtmässigen Zustandes zu entscheiden ist (im gleichen Sinne für den Kanton Appenzell Innerrhoden Urteil 1C_288/2020 vom 28. April 2021 E. 2.2).
Dies hat im vorliegenden Fall zur Folge, dass das nachträgliche Baubewilligungsverfahren mit dem Entscheid des Baudepartements vom 21. April 2020 nicht abgeschlossen ist. Vielmehr hat der Gemeinderat aufgrund des Entscheids des Baudepartements eine neue Anordnung (namentlich) betreffend die Wiederherstellung des rechtmässigen Zustandes zu erlassen. Dabei wird er die Verhältnismässigkeit von Wiederherstellungsmassnahmen betreffend die nicht bewilligten Bauten und Anlagen neu zu beurteilen haben. Hierbei kommt ihm ein gewisser Ermessensspielraum zu. Letzteres gilt selbst unter Berücksichtigung des Umstandes, dass gemäss dem Entscheid des Baudepartements die Terrasse und die Sichtschutzmauer den Strassen- und Wegabstand einzuhalten haben sowie im Zusammenhang mit der Sichtschutzmauer nicht auf das Ausmass der vorbestehenden Holzwand abgestellt werden darf.
Somit ist der Entscheid des Baudepartements als Zwischenentscheid zu qualifizieren. Nachdem das Verwaltungsgericht die dagegen erhobene Beschwerde, soweit es darauf eintrat, abgewiesen hat, stellt der angefochtene Entscheid im Lichte der zitierten Rechtsprechung ebenfalls einen Zwischenentscheid im Sinne von <ref-law> dar (vgl. vorne E. 1.4).
3.
Nach dem Dargelegten bleibt zu prüfen, ob das Urteil des Kantonsgerichts unter den Voraussetzungen von <ref-law> anfechtbar ist.
3.1. Wie erwähnt ist gemäss <ref-law> 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). Da das Bundesgericht eine Sache - wie ausgeführt - grundsätzlich nur einmal beurteilen soll, ist die zweite Voraussetzung einschränkend zu verstehen (<ref-ruling> E. 1.4). Nach konstanter Rechtsprechung haben sodann die Rechtssuchenden im Einzelnen darzulegen, inwiefern die Beschwerdevoraussetzungen nach <ref-law> erfüllt sind. Ansonsten ist auf die Beschwerde mangels hinreichender Begründung nicht einzutreten, sofern die Voraussetzungen nicht klar gegeben sind (<ref-ruling> E. 1.1; <ref-ruling> E. 4; je mit Hinweisen). Ist die Beschwerde gegen einen Zwischenentscheid gemäss <ref-law> 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 (<ref-law>; zum Ganzen: Urteil 1C_288/2020 vom 28. April 2021 E. 3.1).
3.2. Die Beschwerdeführer behaupten zwar, es könnte ihnen aus dem angefochtenen Entscheid ein nicht wieder gutzumachender Nachteil im Sinne von <ref-law> erwachsen. Ein solcher ist aber selbst unter Berücksichtigung der Erwägungen im angefochtenen Entscheid, auf welche die Beschwerdeführer in diesem Kontext verweisen, nicht ersichtlich:
Gemäss ständiger Praxis zu <ref-law> müsste der Nachteil rechtlicher Natur sein und auch durch einen für die rechtssuchende Partei günstigen Endentscheid nachträglich nicht mehr behoben werden können (<ref-ruling> E. 3.6; <ref-ruling> E. 1; <ref-ruling> E. 1.2; je mit Hinweisen). In baurechtlichen Angelegenheiten wird ein nicht wieder gutzumachender Nachteil rechtlicher Natur unter gewissen Umständen insbesondere im Zusammenhang mit einer Beschwerde gegen baurechtliche Vorentscheide bejaht (hierzu BGE <ref-ruling> E. 1.3.4 und 1.3.5). Ein solcher Vorentscheid liegt jedoch nach der dargestellten kantonalrechtlichen Konzeption nicht vor (vgl. vorne E. 2.2). Auch sonst erleiden die Beschwerdeführer durch das angefochtene Urteil keinen nicht wieder gutzumachenden Nachteil. Es steht ihnen offen, einen allfälligen für sie ungünstigen Endentscheid betreffend die Baubewilligung und die Wiederherstellung des rechtmässigen Zustandes (sowie betreffend die Gebührenbemessung) anzufechten. Diesfalls können sie das vorliegend angefochtene Urteil des Verwaltungsgerichts zusammen mit dem Endentscheid anfechten, soweit es sich auf dessen Inhalt auswirkt (<ref-law>). In diesem Zusammenhang können sie gegebenenfalls auch geltend machen, mit diesem Urteil sei zu Unrecht eine vom Baudepartement am 21. April 2020 angeordnete Verschärfung der Wiederherstellungsmassnahmen bestätigt worden.
3.3. Die Beschwerdeführer berufen sich sodann nicht auf <ref-law>. Vielmehr gehen sie selbst davon aus, dass eine Gutheissung der Beschwerde im vorliegenden Fall nicht sofort einen Endentscheid im Sinne von <ref-law> herbeiführen würde. Ob sich bei einer Gutheissung des Rechtsmittels ein bedeutender Aufwand an Zeit oder Kosten ersparen liesse, kann unter diesen Umständen offenbleiben.
Die Beschwerde erweist sich somit auch mit Blick auf <ref-law> als unzulässig.
4.
Nach dem Ausgeführten ist auf die Beschwerde nicht einzutreten. Bei diesem Verfahrensausgang werden die Beschwerdeführer unter solidarischer Haftung kostenpflichtig (Art. 66 Abs. 1 und 5 BGG). Parteientschädigungen sind nicht geschuldet (Art. 68 Abs. 2 und 3 BGG).

Demnach erkennt das Bundesgericht:
1.
Auf die Beschwerde wird nicht eingetreten.
2.
Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern unter Solidarhaft auferlegt.
3.
Dieses Urteil wird den Beschwerdeführern, der Politischen Gemeinde U._, dem Baudepartement des Kantons St. Gallen und dem Verwaltungsgericht des Kantons St. Gallen, Abteilung I, schriftlich mitgeteilt.
Lausanne, 6. Oktober 2021
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Chaix
Der Gerichtsschreiber: König