Sachverhalt: A. Am 8. September 2003 erteilte die Gemeinde Naters die baurechtliche Bewilligung zur Errichtung eines Mehrfamilienhauses auf der Parzelle Nr. 6428. Die von X._, Y._ sowie Mitbeteiligten dagegen erhobenen Beschwerden wiesen der Staatsrat des Kantons Wallis und anschliessend das Kantonsgericht Wallis ab, soweit sie darauf eintraten. Das Bundesgericht trat am 9. August 2005 auf eine von X._, Y._ sowie Mitbeteiligten gegen den Entscheid des Kantonsgerichts erhobene Verwaltungsgerichtsbeschwerde nicht ein und wies die ebenfalls eingereichte staatsrechtliche Beschwerde ab, soweit es darauf eintrat (Urteil 1A.115/2005). Am 8. Dezember 2005 wies das Bundesgericht ein von X._, Y._ sowie Mitbeteiligten eingereichtes Gesuch um Revision des Urteils des Bundesgerichts vom 9. August 2005 ab, soweit darauf einzutreten war (Urteil 1A.255/2005). B. Mit Schreiben vom 26. März 2008 verlängerte die Gemeinde die Geltung der für das Bauprojekt auf der Parzelle Nr. 6428 erteilten Baubewilligung "gestützt auf das Gerichtsurteil vom 8. Dezember 2005 ab dem 5. Dezember 2008 für zwei Jahre". Am 26. September 2010 richteten sich X._, Y._ sowie Mitbeteiligte an die Gemeinde Naters. Sie beantragten, es sei festzustellen, dass die Baubewilligung vom 8. September 2003 inzwischen erloschen sei. Ausserdem sei die Einstellung jeglicher Bautätigkeit auf dem Baugrundstück anzuordnen. Am 11. Oktober 2010 teilte ihnen die Gemeinde mit, sie werde keine Einstellung der Bautätigkeit anordnen. Die Baubewilligung sei um zwei Jahre verlängert worden und folglich noch gültig bis zum 8. Dezember 2010. C. Daraufhin gelangten X._, Y._ sowie Mitbeteiligte mit Beschwerde an den Staatsrat. Sie beantragten wiederum, es sei festzustellen, dass die Baubewilligung vom 8. September 2003 erloschen sei. Sodann seien die Einstellung der sich in Gang befindlichen Arbeiten anzuordnen und fortführende Bauarbeiten bis zum Vorliegen einer neuen Baubewilligung zu untersagen. Mit Entscheid vom 28. September 2011 wies der Staatsrat die Beschwerde ab und stellte fest, dass die Z._ AG mit den Bauarbeiten auf der Parzelle Nr. 6428 in Ausübung der Baubewilligung vom 8. September 2003 zu Recht begonnen habe. Dagegen erhoben X._ und Y._ Beschwerde an das Kantonsgericht. Sie beantragten, es sei festzustellen, dass auf der Parzelle Nr. 6428 ohne gültige Baubewilligung gebaut worden sei bzw. gebaut werde. Es sei zu verfügen, dass das Auflage- und Baubewilligungsverfahren nachzuholen sei und bis zum Vorliegen einer rechtskräftigen Baubewilligung mit der Bautätigkeit nicht fortgefahren werden dürfe. Zufolge der Bautätigkeit im "bewilligungsfreien Raum" sei eine Busse zu verfügen. Auf Gesuch der Z._ AG hin entzog das Kantonsgericht der Beschwerde von X._ und Y._ am 7. Dezember 2011 die aufschiebende Wirkung. Mit Entscheid vom 26. Januar 2012 wies das Kantonsgericht die Beschwerde ab, soweit es auf sie eintrat und die Begehren nicht gegenstandslos geworden waren. D. Gegen die Entscheide des Kantonsgerichts vom 7. Dezember 2011 sowie vom 26. Januar 2012 haben X._ und Y._ am 9. März 2012 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht erhoben. Sie beantragen, der Entscheid vom 7. Dezember 2011 sei vollständig, eventualiter mit Ausnahme von Ziffer 3 und der Entscheid vom 26. Januar 2012 mit Ausnahme von Ziffer 3 aufzuheben. Es sei festzustellen, dass auf der Parzelle Nr. 6428 ohne gültige Baubewilligung gebaut worden sei bzw. gebaut werde. Es sei zu verfügen, dass das Auflage- und Baubewilligungsverfahren nachzuholen sei und bis zum Vorliegen einer rechtskräftigen Baubewilligung mit der Bautätigkeit zumindest teilweise nicht fortgefahren werden dürfe. Einzustellen seien die Arbeiten am grossen Garagenanbau, am Kinderspielplatz, an der Umgebungsgestaltung sowie das Abpumpen des Grundwassers. E. Mit Verfügung vom 11. April 2012 hat das Bundesgericht das von den Beschwerdeführerinnen gestellte Gesuch um aufschiebende Wirkung abgewiesen. F. Die Vorinstanz, der Staatsrat und die Gemeinde Naters beantragen die Abweisung der Beschwerde. Die Beschwerdegegnerin beantragt, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Mit Eingabe vom 14. Mai 2012 halten die Beschwerdeführerinnen an der Beschwerde fest. 