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 Art. 107 Abs. 2 BGG 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. 