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.

Erwägungen:
1. 1.1 Angefochten ist ein kantonal letztinstanzlicher Entscheid, mit welchem auf eine Beschwerde gegen die Baubewilligung für zwei Mehrfamilienhäuser nicht eingetreten wurde, weil die Beschwerdeführer mangels genügender Betroffenheit durch das Bauprojekt nicht zur Beschwerde legitimiert seien. Das Urteil des Verwaltungsgerichts stützt sich mithin auf öffentliches Recht (vgl. <ref-law>) und stellt einen kantonalen Endentscheid dar (vgl. Art. 86 Abs. 1 lit. d und Abs. 2 i.V.m. <ref-law>).
1.2 Die Beschwerdeführer machen u.a. geltend, das Verwaltungsgericht sei auf ihre Beschwerde zu Unrecht nicht eingetreten. Zu dieser Rüge sind sie nach <ref-law> befugt, ungeachtet ihrer Legitimation in der Sache. Auf die rechtzeitig erhobene Beschwerde ist daher grundsätzlich - unter Vorbehalt rechtsgenüglich begründeter Rügen (dazu sogleich E. 1.3 hiernach) - einzutreten.
1.3 Nach <ref-law> ist in der Begründung in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt. Dies setzt voraus, dass sich der Beschwerdeführer wenigstens kurz mit den Erwägungen des angefochtenen Entscheids auseinandersetzt. Genügt die Beschwerdeschrift diesen Begründungsanforderungen nicht, so ist darauf nicht einzutreten. Zwar wendet das Bundesgericht das Recht grundsätzlich von Amtes wegen an (<ref-law>); dies setzt aber voraus, dass auf die Beschwerde überhaupt eingetreten werden kann, diese also wenigstens die minimalen Begründungsanforderungen von <ref-law> erfüllt.
Strengere Anforderungen gelten, wenn die Verletzung von Grundrechten geltend gemacht wird. Dies prüft das Bundesgericht nicht von Amtes wegen, sondern nur insoweit, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (<ref-law>). Für derartige Rügen gelten die gleichen Begründungsanforderungen, wie sie gestützt auf Art. 90 Abs. 1 lit. b OG für die staatsrechtliche Beschwerde gegolten haben (<ref-ruling> E. 1.4.2 S. 254 mit Hinweisen). Die Beschwerdeschrift muss die wesentlichen Tatsachen und eine kurz gefasste Darlegung darüber enthalten, welche verfassungsmässigen Rechte bzw. welche Rechtssätze inwiefern durch den angefochtenen Erlass oder Entscheid verletzt worden sind. Das Bundesgericht prüft nur klar und detailliert erhobene und, soweit möglich, belegte Rügen; auf rein appellatorische Kritik am angefochtenen Entscheid tritt es nicht ein. Wird eine Verletzung des Willkürverbots geltend gemacht, muss anhand der angefochtenen Subsumtion im Einzelnen dargelegt werden, inwiefern der Entscheid an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 1.3 S. 261 mit Hinweisen).
1.4 Nicht zu hören sind die Beschwerdeführer mit dem Antrag, die erteilte Baubewilligung und damit der Beschluss des Gemeinderats vom 8. Januar 2008 sei aufzuheben: Dieser ist durch das Urteil des Verwaltungsgerichts ersetzt worden (Devolutiveffekt) und gilt als inhaltlich mitangefochten (<ref-ruling> E. 1 S. 441 mit Hinweisen).
2. Vorab ist festzuhalten, dass sich das Verwaltungsgericht lediglich mit der Frage auseinanderzusetzen hatte, ob die Beschwerdeführer zur Einsprache im Bauverfahren legitimiert seien. Die materielle Rechtmässigkeit des Bauprojekts war demnach nicht Verfahrensgegenstand. Die Beschwerdeführer verkennen diese Ausgangslage, wenn sie dem Verwaltungsgericht vorwerfen, es habe seine Kognition in unzulässiger Weise eingeschränkt. Die Vorinstanz war nicht gehalten, sich zum eigentlichen Bauprojekt zu äussern. Die entsprechende Rüge der Beschwerdeführer, wonach das Verwaltungsgericht sich übermässige Zurückhaltung auferlegt habe, ist abzuweisen.
3. Weiter werfen die Beschwerdeführer dem Verwaltungsgericht in verfahrensrechtlicher Hinsicht vor, es habe in Missachtung des Öffentlichkeitsprinzips keine mündliche Verhandlung durchgeführt und von einem Augenschein abgesehen. Damit habe es Art. 6 Ziff. 1 EMRK und ihren Anspruch auf rechtliches Gehör verletzt.
3.1 Nach Art. 6 Ziff. 1 EMRK besteht in Verfahren über zivilrechtliche Streitigkeiten ein Anspruch auf öffentliche Verhandlung, sofern die Parteien nicht ausdrücklich oder stillschweigend darauf verzichten. Ein Entscheid über zivilrechtliche Ansprüche im Sinne von Art. 6 Ziff. 1 EMRK liegt unter anderem vor, wenn eine bau- oder planungsrechtliche Massnahme direkte Auswirkungen auf die Ausübung der Eigentumsrechte der Grundeigentümer hat (<ref-ruling> E. 2 S. 45).
§ 17 Abs. 1 der kantonalen Verordnung über die Verwaltungsrechtspflege vom 6. Juni 1974 (VRP/SZ; SRSZ 234.110) sieht zudem vor, dass das Verfahren vor den Verwaltungsbehörden, den selbständigen Rekurskommissionen und dem Verwaltungsgericht unter Vorbehalt abweichender Vorschriften schriftlich ist. Laut Abs. 2 dieser Bestimmung kann die Behörde auf Antrag einer Partei oder von Amtes wegen eine mündliche Verhandlung anordnen.
Aus der sich in den Akten befindlichen Beschwerdeschrift vom 21. Juli 2008 geht hervor, dass die Beschwerdeführer im Verfahren vor dem Verwaltungsgericht wohl die Gewährung des rechtlichen Gehörs und einen Augenschein verlangt, aber nicht explizit um die Durchführung einer öffentlichen Verhandlung ersucht haben. Die vorzitierten Normen wurden nicht verletzt.
3.2 Das rechtliche Gehör gemäss <ref-law> dient einerseits der Sachaufklärung, andererseits stellt es ein persönlichkeitsbezogenes Mitwirkungsrecht beim Erlass eines Entscheides dar, welcher in die Rechtsstellung des Einzelnen eingreift. Dazu gehört insbesondere das Recht des Betroffenen, sich vor Erlass eines solchen Entscheides zur Sache zu äussern, erhebliche Beweise beizubringen, Einsicht in die Akten zu nehmen, mit erheblichen Beweisanträgen gehört zu werden und an der Erhebung wesentlicher Beweise entweder mitzuwirken oder sich zumindest zum Beweisergebnis zu äussern, wenn dieses geeignet ist, den Entscheid zu beeinflussen. Der Anspruch auf rechtliches Gehör umfasst als Mitwirkungsrecht somit alle Befugnisse, die einer Partei einzuräumen sind, damit sie in einem Verfahren ihren Standpunkt wirksam zur Geltung bringen kann (<ref-ruling> E. 3.1 S. 277; <ref-ruling> E. 2b S. 56; <ref-ruling> E. 4b S. 268, mit Hinweisen). Die Verfassungsgarantie steht indes einer vorweggenommenen Beweiswürdigung nicht entgegen. Das Gericht kann auf die Abnahme von Beweisen verzichten, wenn es aufgrund bereits abgenommener Beweise seine Überzeugung gebildet hat und ohne Willkür annehmen kann, seine Überzeugung werde durch weitere Beweiserhebungen nicht geändert (<ref-ruling> E. 5.3 S. 148).
3.3 Wie bereits in E. 2 hiervor erwähnt, hatte das Verwaltungsgericht nur über die Einsprachelegitimation der Beschwerdeführer zu befinden. Zwar wäre auch dazu die Durchführung eines Augenscheins möglich gewesen, um sich von den Distanzen und möglichen Beeinträchtigungen vor Ort ein Bild zu verschaffen; verpflichtet war das Verwaltungsgericht aufgrund der vorstehenden Ausführungen in E. 3.2 indes nicht. Es ist ihm nicht vorzuwerfen, dass es seine Einschätzung aufgrund der Pläne in den Akten vorgenommen hat.
4. Was schliesslich die übrigen Vorbringen der Beschwerdeführer anbelangt, sind sie abzuweisen, soweit überhaupt darauf eingetreten werden: Strittig ist einzig die Frage der Einsprachelegitimation. Dazu hat sich das Verwaltungsgericht unter Zitierung der einschlägigen Praxis eingehend geäussert. Es gelangt zum Schluss, die Beschwerdeführer würden nicht die geforderte besondere Betroffenheit durch das Bauprojekt aufweisen. Die Beschwerdeführer setzen sich mit dieser Argumentation nicht auseinander. Über weite Teile beziehen sie sich auf andere Verfahren oder bringen zivilrechtliche Argumente vor. Damit sind sie nicht zu hören. Es genügt nicht, wenn sie auf bisherige Gestaltungs- und Erschliessungsplanverfahren verweisen, in welchen ihnen die Legitimation zuerkannt worden war. Damit vermögen sie die behauptete Rechtswidrigkeit der Erwägungen im angefochtenen Urteil nicht darzutun. Bezogen auf die konkrete Situation bringen sie zwar stichwortartig ihre Rügen am Bauprojekt selber vor, gehen aber nicht rechtsgenüglich auf die Überlegungen des Verwaltungsgerichts ein. Will aber der Nachbar eine Baubewilligung anfechten, muss er glaubhaft darlegen, dass er namentlich in räumlicher Hinsicht eine besondere Beziehungsnähe zum Streitgegenstand aufweist und dass seine tatsächliche oder rechtliche Situation durch den Ausgang des Verfahrens beeinflusst werden kann (<ref-ruling> E. 1.3.1 S. 252). Indem die Beschwerdeführer etwa geltend machen, das Vorhaben führe zu einer Verunstaltung des Orts- und Landschaftsbilds und zu wohnhygienisch schlechten Verhältnissen, weil es verstärkte Lärm- und Luftimmissionen auslöse, zeigen sie nicht auf, worin ihre besondere Betroffenheit durch das Projekt bestehen soll. Im Gegenteil, ihre Formulierung "auf die Liegenschaft der Beschwerdeführer und die Bewohner und Umgebung hat dies eine erhebliche und unverhältnismässige Auswirkung" vermittelt den Eindruck, dass aus Sicht der Beschwerdeführer nachgerade die gesamte Bevölkerung vom Bauvorhaben betroffen ist. Die Behauptung allein, jemand sei von den Folgen einer Baubewilligung betroffen, genügt jedoch nicht, um die Beschwerdebefugnis zu begründen (dazu auch Urteil 1C_133/2008 des Bundesgerichts vom 6. Juni 2008, E. 2.3). Auf diese Ausführungen ist nicht einzutreten.
5. Daraus folgt, dass die Beschwerde abzuweisen ist, soweit darauf eingetreten werden kann. Ein Entscheid über das neuerliche Gesuch um aufschiebende Wirkung erübrigt sich damit. Bei diesem Verfahrensausgang haben die Beschwerdeführer die Kosten des bundesgerichtlichen Verfahrens zu tragen (<ref-law>). Zudem haben sie die private Beschwerdegegnerin angemessen für ihren Aufwand zu entschädigten (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern auferlegt.
3. Die Beschwerdeführer haben die private Beschwerdegegnerin für das bundesgerichtliche Verfahren unter solidarischer Haftbarkeit mit Fr. 2'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, dem Gemeinderat Morschach, dem Regierungsrat und dem Verwaltungsgericht des Kantons Schwyz, Kammer III, schriftlich mitgeteilt.
Lausanne, 4. Mai 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Féraud Scherrer