Sachverhalt: A. Die Z._ AG reichte am 8. Juni 2007 beim Gemeinderat Morschach ein Baugesuch für die Erstellung zweier Mehrfamilienhäuser mit Tiefgarage auf dem Grundstück KTN 776 in Morschach ein. Nachdem dagegen zwei Einsprachen eingegangen waren, zog die Bauherrin das Gesuch wieder zurück. Hierauf reichte die Z._ AG am 14. September 2007 ein neues Baugesuch ein, wiederum auf dem nämlichen Grundstück und für zwei Mehrfamilienhäuser mit Tiefgarage. Dagegen erhoben die Ehegatten X._ sowie Y._ Einsprache. B. Der Gemeinderat von Morschach trat auf die Eingaben mit Beschluss vom 8. Januar 2008 wegen fehlender Legitimation der Einsprecher nicht ein. Gleichzeitig erteilte er die Baubewilligung für den Neubau unter Auflagen und Bedingungen. C. Gegen den gemeinderätlichen Beschluss gelangten die Einsprecher am 30. Januar 2008 an den Regierungsrat des Kantons Schwyz. Dieser hiess die Beschwerde am 24. Juni 2008 insofern gut, als er den Gemeinderat anwies, das infolge Rückzugs gegenstandslos gewordene erste Bewilligungsverfahren formell abzuschreiben. Im Übrigen wies der Regierungsrat die Beschwerde ab, soweit er darauf eintrat. D. Das hierauf von den Beschwerdeführern angerufene Verwaltungsgericht schützte den Regierungsratsbeschluss mit Urteil vom 20. November 2008, soweit es auf die Vorbringen der Beschwerdeführer eintrat. In Übereinstimmung mit dem Regierungsrat verneinte es die Einsprachelegitimation der Beschwerdeführer. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 8. Januar 2009 beantragen die Ehegatten X._ sowie Y._ die Aufhebung des Verwaltungsgerichtsurteils und der Baubewilligung. Die Sache sei zur Neubeurteilung an die Vorinstanzen zurückzuweisen. Gleichzeitig ersuchen sie um Gewährung der aufschiebenden Wirkung. Die Gemeinde Morschach beantragt, auf die Beschwerde sei nicht einzutreten; denselben Antrag stellt die Z._ AG als private Beschwerdegegnerin. Eventualiter sei die Beschwerde abzuweisen. Der Regierungsrat und das Verwaltungsgericht des Kantons Schwyz schliessen auf Abweisung der Beschwerde, soweit darauf eingetreten werden könne. Sämtliche Beteiligten haben sich zudem zum Gesuch um aufschiebende Wirkung geäussert. Letzteres wies der Präsident der I. öffentlich-rechtlichen Abteilung des Bundesgerichts mit Verfügung vom 5. Februar 2009 ab. Daraufhin gelangten die Beschwerdeführer am 17. März 2009 erneut mit einem gleichlautenden Ersuchen an das Bundesgericht und machten geltend, die Bauherrin habe inzwischen mit den Bauarbeiten begonnen. Es werde problematisch sein, die getätigten Arbeiten ganz oder teilweise rückgängig zu machen. Auch zu diesem Begehren konnten sich nochmals sämtliche Beteiligten vernehmen lassen. Die diesbezüglichen Eingaben sind jeweils den übrigen Beteiligten zur Kenntnisnahme zugestellt worden. In ihrer Replik halten die Beschwerdeführer sinngemäss an ihren Anträgen fest.