Sachverhalt: A. Die Y._ AG ist Eigentümerin der 1'048 m2 grossen Parzelle Nr. 101, Grundbuch Rüthi, die mit einem viergeschossigen Mehrfamilienhaus mit sieben Wohnungen und einer Tiefgarage überbaut ist. Die Liegenschaft, welche sich gemäss dem Zonenplan der Gemeinde Rüthi vom 9. April 1998 in der Wohn-Gewerbezone WG3 befindet, grenzt an das 1'928 m2 grosse Grundstück Nr. 100 von X.a._ und X.b._. Dieses ist mit einem zweigeschossigen Wohnhaus überbaut. Die Zufahrt zur Tiefgarage des Mehrfamilienhauses verläuft entlang der Grenze zum Grundstück von X.a._ und X.b._. Während das Mehrfamilienhaus selbst, die Umfassungswände der Zufahrt und der Deckenabsatz der Tiefgarage erstellt sind, ist die westliche Garagendecke infolge eines Baustopps noch nicht fertig gebaut. B. Z._ reichte als damaliger Eigentümer der Parzelle Nr. 101 am 20. Mai 2009 ein Baugesuch für das genannte Mehrfamilienhaus ein. Es wurden keine Einsprachen erhoben. Der Gemeinderat von Rüthi bewilligte das Gesuch am 9. Juni 2009. Am 23. September 2009 zeigte der Nachbar X.a._ der Baubehörde von Rüthi an, dass die Tiefgarage in Abweichung von der Baubewilligung nicht als unterirdische Baute erstellt werde. Der Gemeinderat war in der Folge ebenfalls der Meinung, dass die Tiefgarage nicht, wie bewilligt, bloss 1,2 m über das gewachsene Terrain hinausrage. Er erliess deshalb umgehend einen Baustopp und forderte die Bauherrschaft am 2. Oktober 2009 auf, für die Projektänderung ein Nachtragsgesuch einzureichen. C. Das Projektänderungsgesuch der Bauherrschaft vom 2. Oktober 2009 lag vom 19. Oktober 2009 bis zum 4. November 2009 öffentlich auf. Gegen die geplante Änderung erhob X.a._ am 26. Oktober 2009 Einsprache. Der Gemeinderat wies die Einsprache am 2. Februar 2010 / 9. März 2010 ab und bewilligte die Projektänderung. Zur Begründung führte er insbesondere aus, die Höhenüberschreitung der Tiefgarage habe auf 13 cm verringert werden können, wobei allerdings die Koten des gewachsenen Bodens nicht mehr exakt hätten ermittelt werden können. In Anbetracht der Kostenschätzung von Fr. 100'000.-- für einen Rückbau werde auf die Wiederherstellung des rechtmässigen Zustands verzichtet. Gegen diesen Beschluss reichte X.a._ am 17. März 2010 Rekurs ans Baudepartement des Kantons St. Gallen ein. Am 23. März 2010 erhob auch die Ehefrau des Einsprechers, X.b._, Rekurs. Das Baudepartement trat mit Entscheid vom 29. April 2011 auf das Rechtsmittel von X.b._ nicht ein. Den Rekurs von X.a._ wies es ab, soweit es darauf eintrat. Das Baudepartement erwog, Gegenstand des Rekursverfahrens bilde einzig die Frage, ob die Einfahrt in die Tiefgarage mit reduzierter Deckenhöhe gemäss Korrekturgesuch bewilligungsfähig sei. Die Abklärungen hätten ergeben, dass die Tiefgarage die Vorgaben für eine unterirdische Baute einhalte. Der Gemeinderat habe damit die Projektänderung, wenn auch mit unzutreffender Begründung, so doch im Ergebnis zu Recht bewilligt. Gegen diesen Rekursentscheid erhoben X.a._ und X.b._ am 16. Juni 2011 Beschwerde ans Verwaltungsgericht des Kantons St. Gallen. Dieses wies die Beschwerde mit Urteil vom 20. März 2012 ab, soweit es darauf eintrat. D. Mit Eingabe vom 23. April 2012 führen X.a._ und X.b._ Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht. Sie beantragen die Aufhebung des Urteils des Verwaltungsgerichts vom 20. März 2012, des Entscheids des Baudepartements vom 29. April 2011 sowie des Entscheids des Gemeinderats vom 2. Februar 2010 / 9. März 2010. Aufzuheben sei des Weiteren die Baubewilligung des Gemeinderats vom 9. Juni 2009 (vgl. Sachverhalt lit. B. hiervor). Eventualiter sei die Sache zu neuem Entscheid an die Vorinstanz zurückzuweisen. Das Verwaltungsgericht beantragt, auf die Beschwerde sei nicht einzutreten, eventualiter sei diese abzuweisen. Die Beschwerdegegner und die Politische Gemeinde Rüthi stellen in ihren Eingaben den Antrag, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. In ihrer Stellungnahme vom 23. September 2012 halten die Beschwerdeführer an ihren Anträgen fest. 