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.

Erwägungen:
1. 1.1 Der angefochtene Entscheid der Vorinstanz ist ein Endentscheid einer letzten kantonalen Instanz (Art. 86 Abs. 1 lit. d BGG). Ihm liegt ein Beschwerdeverfahren über eine Projektänderung für ein Bauvorhaben und damit eine öffentlich-rechtliche Angelegenheit zu Grunde. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten nach Art. 82 lit. a BGG steht auf dem Gebiet des Raumplanungs- und Baurechts zur Verfügung. Ein Ausschlussgrund nach Art. 83 BGG besteht nicht (vgl. <ref-ruling> E. 1.2 S. 251, 409 E. 1.1 S. 411). Die Beschwerdeführer sind durch den angefochtenen Entscheid, mit welchem ihre Beschwerde abgewiesen wurde, besonders berührt und haben ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung. Ihre Beschwerdelegitimation ist gestützt auf Art. 89 Abs. 1 BGG zu bejahen (vgl. <ref-ruling> E. 1.3 S. 252 ff.). Auf die Beschwerde ist unter Vorbehalt der nachfolgenden Erwägungen einzutreten.
1.2 Nicht einzutreten ist auf den Antrag der Beschwerdeführer, den Entscheid des Baudepartements vom 29. April 2011 sowie den Entscheid des Gemeinderats vom 2. Februar 2010 / 9. März 2010 aufzuheben. Unterinstanzliche Entscheide sind mit Beschwerde in öffentlich-rechtlichen Angelegenheiten nicht selbstständig anfechtbar. Sie werden mit Blick auf den Devolutiveffekt durch den Entscheid der letzten kantonalen Instanz ersetzt und gelten mit der dagegen gerichteten Beschwerde als mitangefochten (vgl. <ref-ruling> E. 1.4 S. 144).
1.3 Wie die Vorinstanz zutreffend erwogen hat, liegt dem vorliegenden Verfahren (einzig) die am 2. Februar 2010 / 9. März 2010 bewilligte Projektänderung bzw. jener Teil der Tiefgarage zu Grunde, über den der Gemeinderat am 2. Oktober 2009 einen Baustopp verhängte. Diese nachgesuchte Projektänderung wurde als Ganzes und nicht bloss zum Teil bewilligt. Entgegen den Ausführungen in der Beschwerde liegt insoweit keine unzulässige "Teilbaubewilligung" vor.
Die übrigen, zwischenzeitlich fertig erstellten Teile des Mehrfamilienhauses werden durch die rechtskräftige Baubewilligung vom 9. Juni 2009 abgedeckt. Der in der Beschwerde behauptete formelle Mangel bei der Bewilligungserteilung, wonach die Baubewilligung vom 9. Juni 2009 nebst dem Gemeindepräsidenten nicht vom Gemeinderatsschreiber, sondern von einer Gemeindeangestellten unterschrieben worden sei, würde die Bewilligung nicht ungültig, sondern bloss anfechtbar machen. Eine Anfechtung aber haben die Beschwerdeführer unterlassen. Nichtig wäre die Baubewilligung nur dann, wenn sie einen besonders schweren Mangel aufweisen würde und dieser zudem offenkundig oder zumindest leicht erkennbar wäre. Gemäss Evidenztheorie wird sodann verlangt, dass die Nichtigkeit die Rechtssicherheit nicht ernsthaft gefährdet. Die Voraussetzungen zur Annahme der Nichtigkeit der Baubewilligung vom 9. Juni 2009 sind vorliegend offensichtlich nicht gegeben. Dies gilt insbesondere auch, soweit die Beschwerdeführer eine Verletzung der Bestimmungen zum Ausnützungstransfer rügen.
Die von den Beschwerdeführern behaupteten Abweichungen der Baute von der erteilten Baubewilligung vom 9. Juni 2009 können nicht im vorliegenden Verfahren betreffend die nachgesuchte Projektänderung gerügt werden, sondern müssen separat bei der zuständigen Baubehörde vorgebracht werden, was die Beschwerdeführer im Übrigen auch getan haben.
Die Vorinstanz ist daher zu Recht nicht auf die Vorbringen eingetreten, welche sich auf die Erteilung und Überschreitung der Baubewilligung vom 9. Juni 2009 beziehen.
1.4 Schliesslich ist die Vorinstanz auch auf die (im Verfahren vor Bundesgericht erneut erhobene) Rüge der Beschwerdeführer nicht eingetreten, der Baustopp sei ihnen nicht eröffnet worden. Die Vorinstanz hat ausgeführt, die Beschwerdeführer verhielten sich treuwidrig. Als direkt betroffene Nachbarn hätten sie den weiteren Bauarbeiten für das ganze Vorhaben nicht tatenlos zuschauen und erst intervenieren dürfen, als diese abgeschlossen gewesen seien. Es wäre vielmehr an ihnen gelegen, sich umgehend gegen die vermeintliche Verletzung des Baustopps zur Wehr zu setzen und die Wiederherstellung der Rekursfrist zu verlangen bzw. ein Rechtsmittel zu ergreifen (vgl. angefochtenes Urteil E. 1.6). Mit dieser Argumentation setzen sich die Beschwerdeführer mit keinem Wort auseinander. Die Beschwerde genügt insoweit den Anforderungen von Art. 42 Abs. 2 BGG nicht, weshalb darauf nicht einzutreten ist.
2. 2.1 Betreffend das Rechtsmittel der Beschwerdeführerin hat die Vorinstanz erwogen, die Teilnahme am Rechtsmittelverfahren setze die Beteiligung am vorinstanzlichen Verfahren voraus. Diese Pflicht entfalle nur, wenn keine Möglichkeit dazu bestanden habe oder wenn erst der angefochtene Entscheid die Parteistellung begründe. Die Beschwerdeführerin habe gegen die geplante Projektänderung keine Einsprache erhoben, sondern sich erst im Verlauf des Rekursverfahrens ihres Ehemanns ins Verfahren eingeschaltet. Sie mache nicht geltend und es sei auch nicht ersichtlich, dass sie am Einspracheverfahren nicht hätte teilnehmen können. Nach dem Grundsatz der Einheit des Verfahrens könne eine an sich legitimierte Person ihre Rügen, die sie nicht rechtzeitig erhoben habe, in einem späteren Verfahrensabschnitt nicht mehr nachholen. Das Baudepartement sei daher zu Recht nicht auf ihren Rekurs eingetreten. Die Beschwerde der Beschwerdeführerin gegen den Nichteintretensentscheid sei abzuweisen.
2.2 Die Beschwerdeführerin setzt sich in ihrer Beschwerde nicht substanziiert mit dieser Begründung der Vorinstanz auseinander. Insbesondere macht sie nicht geltend, die tatsächliche Feststellung der Vorinstanz, wonach sie aus eigenem Entschluss oder aus Versehen nicht am Einspracheverfahren teilgenommen habe, sei willkürlich. Die rechtlichen Ausführungen der Vorinstanz sind zutreffend. Die Beschwerde der Beschwerdeführerin ist deshalb abzuweisen, soweit überhaupt darauf eingetreten werden kann.
3. 3.1 Der Beschwerdeführer rügt wie bereits im vorinstanzlichen Verfahren eine Verletzung seiner Ansprüche auf gleiche und gerechte Behandlung (Art. 29 Abs. 1 BV) und auf rechtliches Gehör (Art. 29 Abs. 2 BV) durch das Baudepartement.
3.2 Die Vorinstanz hat ausgeführt, das Baudepartement habe am 16. Juni 2010 einen Augenschein durchgeführt, an dem alle Verfahrensbeteiligten teilgenommen hätten. Im Hinblick auf eine mögliche gütliche Einigung habe das Baudepartement mit der Bauherrschaft eine Besprechung durchgeführt, anlässlich welcher die Bauherrschaft weitere Beweismittel eingebracht habe, um zu belegen, dass die Höhe der unterirdischen Baute mit der vorliegend zu beurteilenden Projektänderung eingehalten werde. Diese daraufhin schriftlich nachgereichten Beweismittel seien allen Verfahrensbeteiligten zur Stellungnahme zugesandt worden. Das Baudepartement habe in der Folge beim kantonalen Tiefbauamt und beim kantonalen Amt für Raumentwicklung und Geoinformation weitere Unterlagen zum Verlauf des gewachsenen Terrains eingeholt und den Verfahrensbeteiligten sodann Gelegenheit gegeben, sich zu den neuen Erkenntnissen zu äussern.
Ausgehend von diesem Verfahrensablauf sei erstellt, dass der Beschwerdeführer im Rekursverfahren fair und rechtsgleich behandelt worden sei, dass er vollumfänglich bei der Beweiserhebung habe mitwirken können, dass er in sämtliche Akten Einblick erhalten habe und dass er zu allen Beweismitteln und -ergebnissen habe Stellung beziehen können. Die Rüge der Verletzung von Art. 29 Abs. 1 und 2 BV sei damit nicht stichhaltig.
3.3 Der Beschwerdeführer setzt sich in seiner Beschwerde nicht mit der vorinstanzlichen Begründung auseinander und bestreitet die Feststellungen der Vorinstanz nicht. Eine Verletzung von Art. 29 Abs. 1 und 2 BV im Verfahren vor dem Baudepartement ist auch nicht ersichtlich. Die Beschwerde erweist sich folglich als unbegründet und ist abzuweisen, soweit überhaupt darauf eingetreten werden kann.
4. 4.1 In materieller Hinsicht bringt der Beschwerdeführer vor, vorliegend sei der Schachtdeckel auf seinem Grundstück verbindlich als massgeblicher Referenzpunkt für die Berechnung der Höhe des gewachsenen Terrains festgelegt worden. Ausgehend hiervon überrage die Deckenoberkante der Tiefgarage das gewachsene Terrain um mehr als die zulässigen 1,2 m.
4.2 Gemäss Art. 56 Abs. 4 des Gesetzes über die Raumplanung und das öffentliche Baurecht des Kantons St. Gallen vom 6. Juni 1972 (BauG/SG; sGS 731.1) können unterirdische Bauten bis zur Grenze gestellt werden, wenn dadurch schutzwürdige Interessen der Nachbarn nicht beeinträchtigt werden. Nach Art. 16 des Baureglements der Gemeinde Rüthi vom 9. April 1998 (BauR/Rüthi) gelten Bauten und Bauteile dann als unterirdisch, wenn sie - innerhalb des ordentlichen kleinen Grenzabstands - überdeckt sind und das gewachsene Terrain inklusiv Überdeckung an keiner Stelle um mehr als 1,2 m überragen.
4.3 Die Vorinstanz hat erwogen, als "gewachsenes Terrain" gelte das natürliche, nicht künstlich gestaltete Gelände. Im Baugesuch vom 20. Mai 2009 fehlten Angaben zum gewachsenen Terrain und zum Niveaupunkt. Mangels verlässlicher Höhenangaben hätten die Beschwerdegegner für die Ausarbeitung der Projektänderung behelfsmässig die Kote eines Schachtdeckels auf dem Grundstück des Beschwerdeführers in der Nähe der Tiefgarage als massgebliche Höhe des gewachsenen Terrains angenommen. Die tatsächlichen Verhältnisse seien jedoch, soweit möglich, von Amtes wegen festzustellen. Die Beschwerdegegner hätten im Rekursverfahren mit den Vermessungen des S._ Büros vom 22. September 2010, der T._ AG vom 22. September 2010 und der U._ AG vom 12. Juni 2009 bzw. 14. Oktober 2009 nachgewiesen, dass das Baugrundstück Nr. 101 ursprünglich generell höher gelegen sei als die Parzelle Nr. 100 des Beschwerdeführers. Die darauf beim kantonalen Tiefbauamt angeforderten Unterlagen hätten diese Vermutung bestätigt. Noch detaillierter zeige die skalierte Intensitätskarte HQ100 (100-jähriges Hochwasserereignis) auf, dass die Liegenschaft der Beschwerdegegner vor Beginn der Bauarbeiten leicht höher gelegen sei als jene des Beschwerdeführers. Aus dem beim kantonalen Amt für Raumentwicklung und Geoinformation beigezogenen digitalen Terrainmodell (DTM-AV) lasse sich schliesslich für den konkreten Fall bis auf eine Genauigkeit von 5 cm folgern, dass die Kote im Bereich der Tiefgarageneinfahrt im Jahr 2004 einen Wert von 425,1 m.ü.M. aufgewiesen habe und damit gegenüber dem Referenzpunkt des herangezogenen Schachtdeckels, der sich auf 424,94 m.ü.M. befinde, um 16 cm höher gelegen sei. Aufgrund dieses Beweisergebnisses sei der Schluss zu ziehen, dass die Deckenoberkante der Tiefgarage gemäss der zu beurteilenden Projektänderung mit einer Kote von 426,27 m.ü.M. mit an Sicherheit grenzender Wahrscheinlichkeit die maximal zulässige Höhe von 1,2 m gemäss Art. 16 BauR/Rüthi einhalte. Selbst bei einer möglichen maximalen Abweichung von 5 cm würde die zulässige Höhe bloss um 2 cm überschritten. Eine solche Abweichung läge noch innerhalb der Bau- und Messtoleranzen. Daraus ergebe sich zusammenfassend, dass die Projektänderung baurechtskonform und deshalb zu bewilligen sei.
4.4 Sachverhaltsfeststellungen können nur gerügt werden, wenn sie offensichtlich unrichtig, d.h. willkürlich (<ref-ruling> E. 1.2.2 S. 252) sind, auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruhen und für den Ausgang des Verfahrens entscheidend sind (Art. 97 Abs. 1 BGG). Ebenso überprüft das Bundesgericht die Auslegung und Anwendung des kantonalen Rechts nur auf Willkür hin. Nach der ständigen Praxis des Bundesgerichts liegt Willkür in der Rechtsanwendung dann vor, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist. Dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, genügt nicht (<ref-ruling> E. 4.1 S. 133; <ref-ruling> E. 1.2 S. 177; <ref-ruling> E. 3.1 S. 473 f.; je mit Hinweisen).
4.5 Der Beschwerdeführer stellt seine Sicht der Dinge sehr eingehend dar. Auf den angefochtenen Entscheid nimmt er hingegen einzig auf den Seiten 19 - 21 seiner Beschwerdeschrift ausdrücklich Bezug, ohne sich dabei jedoch substanziiert mit den Sachverhaltsfeststellungen und der rechtlichen Würdigung der Vorinstanz auseinanderzusetzen. Die rechtlichen Erwägungen der Vorinstanz zur Sachverhaltsfeststellung von Amtes wegen sind korrekt. Der Beschwerdeführer bringt in Bezug auf die vorinstanzliche Beweiswürdigung einzig pauschal vor, das digitale Terrainmodell (DTM-AV) des kantonalen Amts für Raumentwicklung und Geoinformation sei sichtbar manipuliert worden und gebe die tatsächlichen Verhältnisse auf dem Grundstück Nr. 101 nicht wieder. Diese Behauptung begründet der Beschwerdeführer jedoch nicht. Insbesondere legt er nicht dar, weshalb der Schluss der Vorinstanz, dass die Deckenoberkante der Tiefgarage die maximal zulässige Höhe von 1,2 m gemäss Art. 16 BauR/Rüthi einhalte, unhaltbar sein sollte.
4.6 Soweit der Beschwerdeführer wie bereits im vorinstanzlichen Verfahren geltend macht, der Vertreter der Beschwerdegegner habe im kantonalen Verfahren keine gültige Vertretungsvollmacht vorgelegt (Beschwerde S. 20), kann auf die Ausführungen im angefochtenen Urteil (vgl. S. 7 f.) verwiesen werden. Eine willkürliche Anwendung kantonalen Rechts (vorliegend von Art. 26 des Anwaltsgesetzes des Kantons St. Gallen vom 11. November 1993 [sGS 963.70]) wird vom Beschwerdeführer nicht substanziiert gerügt und ist auch nicht ersichtlich.
5. Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Aufgrund ihres Unterliegens sind die bundesgerichtlichen Kosten den Beschwerdeführern aufzuerlegen (Art. 66 Abs. 1 BGG). Diese haben den privaten Beschwerdegegnern eine angemessene Parteientschädigung auszurichten (Art. 68 Abs. 1 und 2 BGG). Die Gemeinde obsiegt in ihrem amtlichen Wirkungskreis, weshalb ihr keine Parteientschädigung zuzusprechen ist (Art. 68 Abs. 3 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern auferlegt.
3. Die Beschwerdeführer haben die Beschwerdegegner für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, der Politischen Gemeinde Rüthi, dem Baudepartement des Kantons St. Gallen und dem Verwaltungsgericht des Kantons St. Gallen schriftlich mitgeteilt.
Lausanne, 29. November 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Stohner