Sachverhalt:
A. Die vom Karlihof nach Malans führende Malanserstrasse quert beim Dorfeingang von Malans das Trassee der Rhätischen Bahn (RhB). Aufgrund des ausgewiesenen Bedürfnisses, die Kreuzung zwischen Bahn und Strasse zu entflechten, wurden 2008 verschiedene Varianten für diese Massnahme untersucht. Dabei wurde eine Lösung mit Führung der RhB über die Malanserstrasse unmittelbar östlich des Bahnhofs Malans gegenüber den Varianten favorisiert, welche die Kantonsstrasse westlich und in grösserer Entfernung vom heutigen Trassee überqueren würden. Für dieses Vorhaben wurde im März 2009 ein Vorprojekt erarbeitet. Später folgte das Auflageprojekt, welches die neue Kantonsstrasse mit Unterquerung der RhB vom Californiahof bis zur Unterdorfstrasse in Malans beinhaltet. Gestützt darauf beschloss die Gemeinde, zwischen dem Geissrückenweg und der neuen Strassenführung die neue Stampfackerstrasse sowie im Trassee der heutigen Kantonsstrasse eine kombinierte Fussgänger-/Fahrradunterführung zu bauen.
B. Vom 5. Oktober bis 5. November 2009 lag das kantonale Auflageprojekt für die Korrektion der Malanserstrasse, Teilstrecke Karlihof Landquart-Malans, Abschnitt RhB-Unterführung Malans, Kilometer 1.06 bis Kilometer 1.38, öffentlich auf. Die Auflagefrist für die beiden kommunalen Baugesuche - einerseits für die Erstellung der Fussgänger- und Fahrradunterführung (Unterdorfstrasse und Landstrasse Malans) und andererseits für den Neubau der Stampfackerstrasse - lief vom 2. bis 22. Oktober 2009.
Am 14. Juni 2010 genehmigte die Regierung des Kantons Graubünden das aufgrund der Einsprachen und Stellungnahmen geänderte Auflageprojekt für die Korrektion der Malanserstrasse unter Auflagen und spezialrechtlichen Bewilligungen. Gleichzeitig wies sie unter anderem die von X._ sowie Eheleute Y._ dagegen erhobene Einsprache im Sinne der Erwägungen ab. Dagegen gelangten die Genannten ans kantonale Verwaltungsgericht mit dem Antrag, den angefochtenen Entscheid aufzuheben und das Projekt RhB-Unterführung inklusive Verlegung der Kantonsstrasse nicht zu genehmigen.
Die Baukommission der Gemeinde Malans wies die gegen den Neubau der Stampfackerstrasse gerichtete Einsprache von X._ sowie Eheleute Y._ am 23. September 2010 ebenfalls ab, soweit sich diese gegen den ausserhalb der Bauzone gelegenen Teil der Stampfackerstrasse richtete und erteilte - gestützt auf die Zustimmung des Amtes für Raumentwicklung - die Bewilligung für den Neubau der Stampfackerstrasse unter Bedingungen und Auflagen. Dieser Entscheid blieb unangefochten und erwuchs in Rechtskraft.
C. Das Verwaltungsgericht des Kantons Graubünden wies die Beschwerde gegen das kantonale Projekt am 9. Dezember 2010 ab.
D. X._ sowie Eheleute Y._ beantragen dem Bundesgericht mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 10. Januar 2011 die Aufhebung des vorerwähnten Urteils. Das aufgelegte Projekt RhB-Bahnunterführung (inklusive Verlegung der Kantonsstrasse) sei nicht zu genehmigen und die Angelegenheit im Sinne von <ref-law> an die Gemeinde Malans, eventualiter ans Verwaltungsgericht zurückzuweisen.
Die Gemeinde Malans schliesst auf Abweisung der Beschwerde. Desgleichen stellen sowohl die RhB AG wie auch die Regierung und das Verwaltungsgericht des Kantons Graubünden je den Antrag, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne.
Die Beschwerdeführer halten in ihrer Replik sinngemäss an ihren Anträgen fest.

Erwägungen:
1. Beim angefochtenen Urteil handelt es sich um einen kantonal letztinstanzlichen Endentscheid (<ref-law>). Der umstrittene Beschluss des Stadtrats betrifft einen kantonalen Sondernutzungsplan, der vor Bundesgericht den Regeln über die Anfechtung von Verfügungen im Sinne von <ref-law> unterworfen ist (vgl. <ref-ruling> E. 3.3 S. 358; <ref-ruling> E. 3b S. 211; je mit Hinweisen). Als Eigentümer des Grundstücks Nr. 1248 (X._), welches von der neuen Strasse durchquert werden soll, und der unmittelbar angrenzenden, mit einem Wohnhaus überbauten Parzelle (Eheleute Y._), haben die Beschwerdeführer ein schützenswertes Interesse an der Aufhebung des angefochtenen Urteils. Auf die frist- und formgerecht eingereichte Beschwerde ist unter Vorbehalt der rechtsgenüglichen Begründung einzutreten.
2. Die Beschwerdeführer rügen zunächst die fehlende Koordination zwischen dem kantonalen und den kommunalen Verfahren. Die beiden Unterführungsprojekte - die Fussgänger-/Fahrradunterführung einerseits und die Strassenunterführung andererseits - seien nicht aufeinander abgestimmt worden. Jeder Ansatz eines Gesamtkonzepts fehle. Dies stelle eine Verletzung von Art. 1 und Art. 2 Abs. 1 RPG dar.
2.1 Das Gebot der Koordination von raumplanerischen und umweltrechtlichen Verfahren verlangt in materieller Hinsicht, dass die Rechtsanwendung inhaltlich abgestimmt werde, wenn für die Verwirklichung eines Projekts verschiedene materiellrechtliche Vorschriften anzuwenden sind und zwischen diesen Vorschriften ein derart enger Sachzusammenhang besteht, dass sie nicht getrennt und unabhängig voneinander angewendet werden dürfen (<ref-ruling> E. 5 S. 409). In formeller Hinsicht folgt aus der Koordinationspflicht, dass dort, wo für die Errichtung oder Änderung einer Baute Verfügungen mehrerer Behörden nötig sind, eine Behörde zu bezeichnen ist, die für ausreichende Koordination zu sorgen hat (vgl. Art. 25a Abs. 1 RPG; Bundesgesetz über die Koordination und Vereinfachung von Entscheidverfahren vom 18. Juni 1999, AS 1999 S. 3071 ff.). So sind unter anderem die Gesuchsunterlagen gemeinsam öffentlich aufzulegen und dürfen die Verfügungen keine Widersprüche enthalten (Art. 25a Abs. 2 lit. b und Abs. 3 RPG). Zur formellen Koordination gehört grundsätzlich auch, dass anschliessend an die verfahrensrechtlich und zeitlich verbundene Eröffnung der Bewilligungen ein einheitliches Rechtsmittelverfahren durchgeführt wird. Ein solches ist indessen - wie schon in <ref-ruling> E. 6d/aa S. 88 festgehalten worden ist - dann nicht möglich, wenn die zur Bewilligung eines Vorhabens massgeblichen Rechtsfragen teils durch Bundes- und teils durch kantonale Behörden zu beurteilen sind. Ein einheitliches Rechtsmittelverfahren fällt demnach ebenfalls ausser Betracht, wenn die projektierte Baute oder Anlage nach der gesetzlichen Regelung aus einem dem kantonalen und einem dem eidgenössischen Recht unterliegenden Teil besteht und eine Ausdehnung der einen oder anderen Kompetenz nicht möglich ist (siehe dazu das Urteil 1A.141/2006 des Bundesgerichts vom 27. September 2006 E. 5). In diesen Fällen beschränkt sich die Koordination auf eine inhaltlich abgestimmte Rechtsanwendung.
2.2 Vorliegend geben die beteiligten Behörden zu Recht zu bedenken, dass nicht ein einziges Vorhaben zu beurteilen war, sondern dass es sich um zwei verschiedene Projekte auf unterschiedlichen Ebenen handelt. Einerseits geht es um die heute zur Diskussion stehende Korrektion der Kantonsstrasse, andererseits um eine von der Gemeinde zu erstellende Fussgänger- und Fahrradunterführung. Zwar ist der sachliche Zusammenhang zwischen den beiden Vorhaben offensichtlich. Das Verwaltungsgericht hat diesen jedoch zu Recht als nicht derart eng bezeichnet, dass den Beschwerdeführern aus der bemängelten fehlenden Koordination ein Nachteil entstehen würde. Würde der Genehmigungsentscheid der Regierung zum Kantonsstrassenprojekt aufgehoben, so würde auch das kommunale Projekt für die Fussgänger- und Radfahrerunterführung hinfällig. Das kantonale Vorhaben kann aber selbstständig und ohne Bezugnahme auf die Pläne der Gemeinde auf seine Recht- und Zweckmässigkeit hin beurteilt und realisiert werden. Eine Abhängigkeit zwischen den Projekten besteht höchstens auf der Seite der Gemeinde, was aber die Beschwerdeführer nicht tangiert. Wird die Genehmigung des Regierungsrats für die neue Führung der Kantonsstrasse bestätigt, bleibt es den Beschwerdeführern unbenommen, gegen das Bauvorhaben der Gemeinde den Rechtsweg zu beschreiten.
Im Rahmen der kantonalen Genehmigung wurden die Zusatzbewilligungen der involvierten Fachstellen eingeholt und der formellen Koordination Genüge getan.
2.3 Unbegründet sind auch die Vorwürfe der Beschwerdeführer, es mangle an einem Gesamtverkehrskonzept. Die Gemeinde hat eine Machbarkeitsstudie in Auftrag gegeben, welche verschieden Varianten beleuchtet hat (Beilage 8 der Gemeinde im vorinstanzlichen Verfahren). Was die Beschwerdeführer dagegen vorbringen, sind unbelegte Behauptungen. Weshalb etwa die beauftragten Planungsbüros nicht unabhängig sein sollen, ist nicht ersichtlich. Im aufgelegten Technischen Bericht vom September 2009 (Beilage 2 der Regierung im vorinstanzlichen Verfahren) wird geschildert, dass die Gemeinde, die RhB und das kantonale Tiefbauamt bei der Erarbeitung des aufgelegten Vorhabens zusammengearbeitet haben. Auch in der Botschaft für die Gemeindeversammlung vom 3. Dezember 2009 wurde eine enge Zusammenarbeit zwischen Verkehrsplaner, Ingenieurbüro sowie Vertretern des Kantons, der RhB und der Gemeinde erwähnt (Beilage 2 der Gemeinde im vorinstanzlichen Verfahren). Dies wird aus den Überlegungen zu den einzelnen Varianten denn auch deutlich. Die von den Behörden favorisierten beiden Unterführungen sind aufeinander abgestimmt und die Vor- und Nachteile gegeneinander abgewogen worden.
Ein Verstoss gegen das Koordinationsgebot ist infolgedessen zu verneinen.
3. Weiter stellen die Beschwerdeführer das öffentliche Interesse am umstrittenen Projekt in Abrede. Sie machen überdies geltend, die fehlende Abklärung einer offensichtlich praktikablen Variante sei willkürlich und habe ihr Stimmrecht, das ihnen einen Anspruch auf sachliche, richtige und umfassende Information gewährleiste, verletzt.
3.1 Das Verwaltungsgericht führt als öffentliches Interesse einerseits die Entflechtung von Bahn und Strasse - und in diesem Zusammenhang die Unfallgefahr - an. Sodann gebe es ein öffentliches Interesse an einer ungestörten Erschliessung der Gemeinde Malans. Wenn die Barrieren pro Stunde 20 Minuten geschlossen seien, würden der private und der öffentliche Verkehr sowie der öffentliche Dienst (Notfalldienst, Feuerwehr, Winterdienst etc.) auf dieser prioritären Erschliessungsstrasse stark behindert. Auch die Trennung des motorisierten vom nicht motorisierten Langsamverkehr könne ohne Willkür als im öffentlichen Interesse liegend beurteilt werden. Für überzeugend hält das Verwaltungsgericht zudem, dass die für den motorisierten Verkehr vorgesehene Unterführung auf dem heutigen Trassee nur möglich wäre, wenn der nördliche Ausläufer zirka 130 m ins Dorf hineinreichen würde. Indessen betrage die Distanz zwischen Bahnübergang und der Einmündung der Bahnhofstrasse in die Unterdorfstrasse nur ca. 40 m. Somit müsse, wenn verhindert werden solle, dass der nördliche Ausläufer der Unterführung diesen Teil des Dorfs praktisch entzwei schneide, eine andere Linienführung gewählt werden. Die Einwendungen, das Stampfackerquartier sei bereits genügend erschlossen, habe die Gemeinde widerlegt und dargetan, dass der grösste Teil des durch die neue Unterführung entstehenden Kulturlandverlusts durch den ohnehin notwendigen Neubau der Stampfackerstrasse gleichwohl entstehen würde. Die Gemeindeversammlung habe mit grossem Mehr für das vorliegende Konzept gestimmt, wogegen die privaten Interessen der Beschwerdeführer nicht ankämen.
3.2 Die Beschwerdeführer legen in erster Linie ihren Standpunkt dar. Selbstredend favorisieren sie ein Projekt ohne Tangierung ihrer Parzellen. Damit ist aber das öffentliche Interesse an der nun zur Diskussion stehenden Lösung nicht widerlegt. Die vom Verwaltungsgericht vorgenommene Würdigung ist nicht zu beanstanden. Entgegen des Eindrucks, den die Beschwerdeführer vermitteln, wurden mehrere Linienführungen geprüft und aufgezeigt, welche Vor- und Nachteile damit verbunden sind. Aus der Botschaft für die Gemeindeversammlung vom 3. Dezember 2009 geht dies unmissverständlich hervor. Darin werden sämtliche Varianten geschildert. Laut Protokoll der erwähnten Gemeindeversammlung (Beilage 11 der Gemeinde im vorinstanzlichen Verfahren) wurden diese diversen Lösungsmöglichkeiten sowie deren Vor- und Nachteile am 3. Dezember 2009 den Anwesenden erläutert. Die nachfolgende Diskussion drehte sich nachgerade um die unterschiedlichen Varianten. Weshalb das Stimmrecht der Beschwerdeführer verletzt worden sein soll, ist weder ersichtlich noch wurde dies rechtsgenüglich dargetan. Den Ausführungen des Verwaltungsgerichts kann gefolgt werden.
3.3 Im Zusammenhang mit dem aus ihrer Sicht fehlenden öffentlichen Interesse bringen die Beschwerdeführer vor, Malans als Dorf sei im Bundesinventar der schützenswerten Ortsbilder von nationaler Bedeutung (ISOS) aufgenommen. Der massive Eingriff mit zwei Bahnunterführungen und neuen Zufahrtsstrassen respektiere in keiner Weise die nationalen Interessen des ISOS.
3.4 Im ISOS-Inventar wird das Ortsbild von Malans wie folgt umschrieben:
"Die sehr hohen räumlichen Qualitäten ergeben sich einerseits durch das äussere Ortsbild, die Art und Weise wie der Ort in die Topographie eingebettet ist, andererseits durch die klare sternförmige Anordnung der dicht bebauten, nach aussen strebenden Gassen rund um das locker bebaute, grosse Freiräume aufweisende Zentrum."
3.5 Die Regierung hat die kantonale Denkmalpflege im Bewilligungsverfahren angehört und deren Bedenken weitgehend Rechnung getragen. So muss bei der Detailprojektierung ein ausgewiesener Fachmann als Berater beigezogen werden. Damit soll sichergestellt werden, dass die geplante Unterführung unter grösstmöglicher Schonung des Ortsbilds erstellt wird. In ihrem Entscheid vom 14. Juni 2010 hat sich die Regierung in E. 4 auf Art. 15 des kantonalen Strassengesetzes vom 1. September 2005 (StrG/GR; BR 807.100) berufen, wonach Kantonsstrassen nach den jeweiligen Erkenntnissen der Bau- und Verkehrstechnik und unter Beachtung der zu erwartenden Nutzung, mit guter Einordnung in die bauliche und landschaftliche Umgebung, möglichst umweltschonend sowie wirtschaftlich zu projektieren und zu bauen sind. Dabei sei immer auch eine Interessenabwägung vorzunehmen. Vorliegend diene die Unterführung nicht nur einer Komfortsteigerung, sondern bezwecke in erster Linie die Erhöhung der Verkehrssicherheit für alle Verkehrsteilnehmer. Als weiterer Grundsatz halte Art. 15 Abs. 2 StrG fest, dass Kantonsstrassen grundsätzlich verkehrsorientiert sind. Verkehrsorientierte Strassen bildeten das übergeordnete Netz und ermöglichten eine sichere, leistungsfähige und wirtschaftliche Mobilität. Sie seien primär auf die Anforderungen des Motorfahrzeugverkehrs auszurichten. An der vorgesehenen Linienführung werde darum festgehalten und der beantragte Verzicht auf die Strassenunterführung abgelehnt.
3.6 Die Vorinstanzen durften das Interesse an einer verkehrssicheren, leistungsfähigen Strassenführung dem ungeschmälerten Erhalt des Ortsbilds überordnen, zumal jede neue Verkehrsführung zu einem Eingriff in bestehende Strukturen führt. Bei einer Unterführung am jetzigen Standort wäre beispielsweise eine wesentlich längere Rampe ins Dorf nötig gewesen. Insgesamt ist die vorgenommene Interessenabwägung nicht zu beanstanden (vgl. etwa das Urteil 1C_492/2009 des Bundesgerichts vom 20. Juli 2010 E. 5.5), wohingegen die Vorhalte der Beschwerdeführer in pauschaler Weise erfolgen, ohne eine Verfassungs- oder Bundesrechtsverletzung rechtsgenüglich aufzuzeigen.
4. Schliesslich mangelt es dem Projekt nach Meinung der Beschwerdeführer an der Verhältnismässigkeit. In erster Linie gehe es um den Komfort und nicht um eine notwendige Projektierung.
4.1 Auch in diesem Zusammenhang erschöpft sich die Beschwerde über weite Teile in appellatorischer Kritik, ohne dass sie die Rechtmässigkeit der gewählten Streckenführung ernsthaft in Zweifel zu ziehen vermag. Die Beschwerdeführer wehren sich gar nicht gegen eine Unterführung für den motorisierten Verkehr, nur gegen eine am geplanten Ort. Dies ist verständlich, werden doch ihre Parzellen dadurch in Mitleidenschaft gezogen. Dies genügt indes nicht, um aufzuzeigen, dass das Projekt unverhältnismässig wäre.
4.2 Bereits im Rahmen der Ortsplanung im Oktober 2006 wurde die Schliessung der Barriere in einem Gutachten zu Verkehrsfragen des Büros Hartmann & Sauter, Chur, thematisiert (Beilage 9 der Gemeinde im vorinstanzlichen Verfahren). Dabei wurde deutlich, dass es sich nicht um kurze, gelegentliche Verkehrsbehinderungen handelt, sondern dass die Barriere bereits damals gemäss dem Fahrplan 2005 während der Hauptsaison ca. 80 Mal täglich und während der Nebensaison ca. 60 Mal täglich geschlossen wurde. Die mittlere Schliesszeit betrug 2003 zwei Minuten, die längste fast sechs Minuten. Mit Blick darauf, dass die RhB kapazitätsmässig noch ausgebaut werden soll, ist es der Gemeinde nicht vorzuwerfen, dass sie eine Lösung dieser Situation als notwendig erachtet. Zwar berufen sich die Beschwerdeführer auf das Gutachterbüro, welches in seinem Bericht S. 2 festgehalten hat, die Frage einer niveaufreien Bahnüberquerung sei keine Frage der Leistungsfähigkeit, sondern eine Frage des Komforts - und der Sicherheit. Das Satzende mit dem Hinweis auf den Sicherheitsaspekt haben die Beschwerdeführer bei ihrem Zitat weggelassen. Dass eine Unterführung im Vergleich zu einer Bahnquerung wesentlich zur Verbesserung der Verkehrssicherheit beiträgt, wird von den Beschwerdeführern nicht ernsthaft bestritten.
4.3 Bereits in den vorstehenden Erwägungen wurde gezeigt, dass verschiedene Varianten geprüft und auch den Stimmbürgern zur Kenntnis gebracht wurden. Die von den Beschwerdeführern offenbar favorisierte Lösung mit einer Unterführung im heutigen Trassee der Landstrasse wurde dabei ebenfalls berücksichtigt und verworfen, weil lange und steile Rampen (Gefälle von 11%) beidseits der Unterführung notwendig würden, keine direkte Anbindung der Bahnhofstrasse an das Unterdorf mehr möglich wäre, ein Teilabbruch der Häuser westlich des Unterdorfs bzw. der Landstrasse notwendig würde und kein Platz vorhanden wäre für eine separate Fussgänger- und Radfahrerunterführung (Machbarkeitsstudie S. 11). Unter anderem der Eingriff in privates Eigentum wäre damit einschneidender gewesen als bei der nun gewählten Lösung. Die Beschwerdeführer bringen dagegen keine überzeugenden Argumente vor, sondern beharren auf ihrem Standpunkt, es sei keine ernsthafte Alternative zum umstrittenen Projekt gesucht worden und ein Ausbau mit Unterführung unter Beibehaltung der bisherigen Streckenführung wäre technisch möglich. Sie äussern zwar harsche Kritik an der Machbarkeitsstudie, legen aber nicht dar, worin deren Mängel detailliert bestehen sollen. Damit ist den Begründungsanforderungen nicht Genüge getan.
4.4 Insgesamt kann auf die schlüssigen Ausführungen des Verwaltungsgerichts im angefochtenen Entscheid (E. 5 des Urteils vom 9. Dezember 2010) verwiesen werden (<ref-law>). Das Projekt hält vor dem Verhältnismässigkeitsprinzip statt.
5. Die Beschwerde ist demnach abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Verfahrensausgang haben die Beschwerdeführer für die vor Bundesgericht entstandenen Kosten aufzukommen (<ref-law>). Zudem haben sie die private Beschwerdegegnerin für das bundesgerichtliche Verfahren angemessen zu entschädigen (<ref-law>).

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 private Beschwerdegegnerin für das bundesgerichtliche Verfahren unter solidarischer Haftbarkeit mit insgesamt Fr. 3'000.-- zu entschädigen.
4. Dieses Urteil wird den Beschwerdeführern, der Regierung des Kantons Graubünden, der Gemeinde Malans, der weiteren Beteiligten und dem Verwaltungsgericht des Kantons Graubünden, 5. Kammer, schriftlich mitgeteilt.
Lausanne, 26. April 2011
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Fonjallaz Scherrer Reber