Sachverhalt:
A. Die Eheleute Z._ sind Eigentümer der Parzelle Nr. 395 in Falera, welche über die Quartierstrasse Via Suriet (Parzelle Nr. 465-T) erschlossen wird. Gegen die Einleitung einer Quartierplanung für das Gebiet "Er Liung", das auch die Parzelle Nr. 395 umfasst, führte X.Z._ Rekurs beim Verwaltungsgericht des Kantons Graubünden. Im Laufe des Verfahrens kam es zu einer gütlichen Einigung zwischen der Gemeinde Falera und X.Z._, worauf dieser das Rechtsmittel zurückzog. Mit Präsidialverfügung vom 22. Januar 1998 schrieb das Verwaltungsgericht das Rekursverfahren ab, wobei es den Vergleich zwischen X.Z._ und der Gemeinde Falera mit folgendem Wortlaut in die Erwägungen aufnahm:
1. Die Gemeinde Falera hat für das Gebiet Er Liung eine Quartierplanung eingeleitet.
2. Beim Verwaltungsgericht des Kantons Graubünden ist ein Rekurs von Herrn X.Z._ gegen diesen Einleitungsbeschluss hängig. Die Parteien erledigen das pendente Rekursverfahren durch vorliegenden Vergleich.
3. Herr X.Z._ zieht den Rekurs gegen die Einleitung der Quartierplanung zurück.
4. Der Vorstand der Gemeinde Falera verpflichtet sich zu folgenden Handlungen:
a) Im Rahmen der künftigen Quartierplanung die Parzelle Nr. 395 weder mit Planungs- noch Erschliessungskosten zu belasten, ausgenommen sind die Kosten gemäss lit. b und weitere Aufwendungen im Auftrage und Interesse des Eigentümers.
b) Die Liegenschaft Nr. 395 mit einer Treppe an die Quartierstrasse anzuschliessen.
c) Vor Beginn der Bauarbeiten an der Strasse den baulichen Zustand der Liegenschaft des Rekurrenten auf eigene Kosten aufnehmen zu lassen.
d) Die Zufahrt zur Garage auf Parzelle Nr. 395 muss erhalten bleiben.
In der Folge wurde der Quartierplan "Er Liung" öffentlich aufgelegt und 1999 genehmigt. Er sieht eine neue Erschliessungsstrasse vor, die oberhalb der Parzelle Nr. 395 verläuft und die Via Suriet unterbricht.
Am 27. März 2009 wurde das Projekt "Quartiererschliessung Er Liung, 2. Etappe, auf Parzelle 1439 in Vallà" öffentlich aufgelegt. Die Gemeinde Falera wies mit Verfügung vom 30. Juni 2009 eine von den Eheleuten Z._ erhobene Einsprache ab und erteilte die Baubewilligung. Gegen diese Verfügung führten die Eheleute Z._ Beschwerde vor dem Verwaltungsgericht des Kantons Graubünden. Mit Urteil vom 11. September 2009 wies dieses das Rechtsmittel ab.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten und subsidiärer Verfassungsbeschwerde vom 8. Oktober 2009 an das Bundesgericht beantragen die Eheleute Z._ im Wesentlichen, das Urteil des Verwaltungsgerichts sei aufzuheben und ihre Einsprache sei zu schützen. Die Gemeinde Falera sei anzuhalten, die Zu- und Wegfahrt auf die Parzelle Nr. 395 über die Via Suriet wie bisher zu gewährleisten.
Das Verwaltungsgericht und die Gemeinde Falera beantragen in ihrer jeweiligen Vernehmlassung die Abweisung der Beschwerden, soweit darauf einzutreten sei. In ihrer Stellungnahme dazu halten die Beschwerdeführer an ihren Anträgen und Rechtsauffassungen fest. Mit Präsidialverfügung vom 5. November 2009 hat das Bundesgericht der Beschwerde die aufschiebende Wirkung zuerkannt.

Erwägungen:
1. 1.1 Dem angefochtenen Entscheid liegt ein Beschwerdeverfahren über eine baurechtliche Bewilligung zu Grunde. Nach Art. 34 Abs. 1 RPG (SR 700) gelten für die Rechtsmittel an die Bundesbehörden die allgemeinen Bestimmungen über die Bundesrechtspflege. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten nach <ref-law> steht auf dem Gebiet des Raumplanungs- und Baurechts zur Verfügung. Das Bundesgerichtsgesetz enthält keinen Ausschlussgrund (<ref-law>). Angefochten ist ein Entscheid einer letzten kantonalen Instanz, welcher das Verfahren abschliesst (Art. 86 Abs. 1 lit. d, Art. 90 BGG). Die Beschwerdeführer haben am vorinstanzlichen Verfahren teilgenommen, sind als Nachbarn durch den angefochtenen Entscheid besonders berührt und haben ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung (<ref-law>). Auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist einzutreten.
1.2 Die Beschwerdeführer erheben gleichzeitig subsidiäre Verfassungsbeschwerde (<ref-law>). Dabei rügen sie die Verletzung von verfassungsmässigen Rechten, welche sie auch mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten hätten geltend machen können (<ref-law>). Die subsidiäre Verfassungsbeschwerde erweist sich deshalb als unzulässig (<ref-law>), kann jedoch vorliegend in eine Beschwerde in öffentlich-rechtlichen Angelegenheiten konvertiert werden. Die unrichtige Bezeichnung des Rechtsmittels schadet den Beschwerdeführern nicht (<ref-ruling> E. 1.2 S. 382; <ref-ruling> E. 3.1 S. 399; je mit Hinweisen).
1.3 Der rechtserhebliche Sachverhalt geht aus den Akten hinreichend hervor. Auf die Durchführung eines Augenscheins kann daher verzichtet werden.
2. 2.1 Die Beschwerdeführer machen eine Verletzung des Grundsatzes von Treu und Glauben geltend (<ref-law>). Sie seien in ihrem Vertrauen in den Vergleich mit der Gemeinde zu schützen. Das Bauprojekt laufe diesem Vergleich zuwider, denn mit der geplanten Rampe wäre es nicht mehr möglich, mit einem Auto auf der Via Suriet zu wenden. Vielmehr müsste in Zukunft entweder die Berg- oder die Talfahrt auf der steilen Strasse im Rückwärtsgang bewältigt werden. Dies sei gefährlich. Die Zufahrt zur Garage auf der Parzelle Nr. 395 würde damit nicht wie vereinbart erhalten bleiben.
2.2 Die Vorinstanz ist der Ansicht, der Einwand der Beschwerdeführer sei verspätet. Der Quartierplan sei im Jahr 1999 genehmigt worden. Die projektierte Rampe, welche neu die Fahrt ab der Einfahrt zur Parzelle Nr. 395 nord- bzw. aufwärts auf der Via Suriet verhindere, sei darin bereits enthalten gewesen. Es müsse heute davon ausgegangen werden, dass die umstrittene Vertragsklausel den Beschwerdeführern nur noch insofern die Zufahrt zur Garage auf Parzelle Nr. 395 gewähre, als sie sich mit der Quartierplanung "Er Liung" vereinbaren lasse.
2.3 Die Rechtmässigkeit eines Zonenplans kann grundsätzlich nur im Anschluss an seinen Erlass bestritten werden. Eine spätere (vorfrageweise) Anfechtung auf einen Anwendungsakt hin ist nur in Ausnahmefällen zulässig, so wenn sich der Betroffene bei Planerlass noch nicht über die ihm auferlegten Beschränkungen Rechenschaft geben konnte oder er im damaligen Zeitpunkt keine Möglichkeit hatte, seine Interessen zu verteidigen (<ref-ruling> E. 3a S. 342; <ref-ruling> E. 5c S. 486; je mit Hinweisen). Das Verwaltungsgericht geht auf die Frage nach der Zulässigkeit der vorfrageweisen Anfechtung nicht ein. Es verneint sie jedoch im Ergebnis, indem es erwägt, die Beschwerdeführer hätten die Frist zur Anfechtung des Gestaltungsplans verpasst. Wie es sich damit verhält, kann offen bleiben, sofern der Grundsatz des Vertrauensschutzes die Berücksichtigung der Vereinbarung trotz unterlassener Anfechtung des Gestaltungsplans verlangt. Dies ist im Folgenden zu prüfen.
2.3 Die Rechtmässigkeit eines Zonenplans kann grundsätzlich nur im Anschluss an seinen Erlass bestritten werden. Eine spätere (vorfrageweise) Anfechtung auf einen Anwendungsakt hin ist nur in Ausnahmefällen zulässig, so wenn sich der Betroffene bei Planerlass noch nicht über die ihm auferlegten Beschränkungen Rechenschaft geben konnte oder er im damaligen Zeitpunkt keine Möglichkeit hatte, seine Interessen zu verteidigen (<ref-ruling> E. 3a S. 342; <ref-ruling> E. 5c S. 486; je mit Hinweisen). Das Verwaltungsgericht geht auf die Frage nach der Zulässigkeit der vorfrageweisen Anfechtung nicht ein. Es verneint sie jedoch im Ergebnis, indem es erwägt, die Beschwerdeführer hätten die Frist zur Anfechtung des Gestaltungsplans verpasst. Wie es sich damit verhält, kann offen bleiben, sofern der Grundsatz des Vertrauensschutzes die Berücksichtigung der Vereinbarung trotz unterlassener Anfechtung des Gestaltungsplans verlangt. Dies ist im Folgenden zu prüfen.
2.4 2.4.1 Der in <ref-law> verankerte Grundsatz von Treu und Glauben statuiert ein Verbot widersprüchlichen Verhaltens und verleiht einer Person Anspruch auf Schutz des berechtigten Vertrauens in behördliche Zusicherungen oder sonstiges, bestimmte Erwartungen begründendes Verhalten der Behörden. Voraussetzung für eine Berufung auf Vertrauensschutz ist, dass die betroffene Person sich berechtigterweise auf die Vertrauensgrundlage verlassen durfte und gestützt darauf nachteilige Dispositionen getroffen hat, die sie nicht mehr rückgängig machen kann. Die Berufung auf Treu und Glauben scheitert sodann, wenn ihr überwiegende öffentliche Interessen entgegenstehen (<ref-ruling> E. 6 S. 636 ff.; <ref-ruling> E. 4.1 S. 170; je mit Hinweisen).
2.4.2 Vertrauensgrundlage bildet vorliegend der Vertrag zwischen der Gemeinde Falera und X.Z._, wie er in die Präsidialverfügung vom 22. Januar 1998 des Verwaltungsgerichts Eingang fand (vgl. dazu <ref-ruling> E. 4a S. 514, wonach es geradezu im Wesen jedes Vertrages liegt, Vertrauen im Hinblick auf das zukünftige Verhalten des Vertragspartners zu begründen). Vertragsgegenstand sind die Beendigung eines öffentlich-rechtlichen Rekursverfahrens und verschiedene Verpflichtungen der Gemeinde Falera im Zusammenhang mit der Erschliessung im Rahmen einer Quartierplanung. Dabei handelt es sich um Fragen des öffentlichen Rechts, weshalb dem Vertrag öffentlich-rechtlicher Charakter zukommt (<ref-ruling> E. 2a und 2b S. 253 f. mit Hinweisen). Die Zulässigkeit der vertraglichen Vereinbarung wird weder von der Vorinstanz noch von der Beschwerdegegnerin in Frage gestellt und es drängen sich diesbezüglich auch keine Zweifel auf (vgl. zur Publ. bestimmtes Urteil 1C_501/2009 vom 4. Januar 2010 E. 4.1 mit Hinweisen).
Öffentlich-rechtliche Verträge sind grundsätzlich gleich wie privatrechtliche nach Treu und Glauben (Vertrauensprinzip) auszulegen. Das bedeutet, dass einer Willensäusserung der Sinn zu geben ist, den ihr der Empfänger aufgrund der Umstände, die ihm im Zeitpunkt des Empfangs bekannt waren oder hätten bekannt sein müssen, in guten Treuen beilegen durfte und beilegen musste. Bei der Auslegung öffentlich-rechtlicher Verträge ist dabei - im Rahmen des Vertrauensprinzips - zu berücksichtigen, dass die Verwaltung beim Vertragsabschluss dem öffentlichen Interesse Rechnung zu tragen hat (<ref-ruling> E. 4e S. 335 f. mit Hinweisen). Das Bundesgericht prüft die Auslegung öffentlich-rechtlicher Verträge, die sich auf kantonales Recht stützen, unter dem Blickwinkel des Willkürverbots (vgl. <ref-ruling> E. 1a/bb S. 331 f. und E. 3a S. 333 f. mit Hinweisen; Urteil 1C_207/2008 vom 20. Februar 2009 E. 4.2).
Wortlaut und Zweck der im Zentrum stehenden Vertragsbestimmung sind, insoweit vorliegend von Bedeutung, klar. Die Gemeinde Falera verpflichtete sich, die Zufahrt zur Garage auf Parzelle Nr. 395 zu erhalten. Für die Auslegung einer Vertragsbestimmung kann weiter das Verhalten der Parteien nach Vertragsabschluss bedeutsam sein. Dieses ist jedoch nur insofern zu berücksichtigen, als es Rückschlüsse auf die Willenslage bei Vertragsabschluss erlaubt (vgl. zum Privatrecht Wolfgang Wiegand, in: Basler Kommentar, Obligationenrecht, 4. Aufl. 2007, N. 29 zu <ref-law>). Das ist hier nicht der Fall. Der blosse Umstand, dass die Beschwerdeführer es unterliessen, gegen den Quartierplan ein Rechtsmittel zu ergreifen, lässt keinen derartigen Rückschluss zu.
2.4.3 Die Beschwerdeführer haben sich berechtigterweise darauf verlassen, dass die Gemeinde Falera die Zufahrt zur Parzelle Nr. 395 erhalten werde. Sie durften davon ausgehen, dass der öffentlich aufgelegte Gestaltungsplan nicht dem kurz zuvor abgeschlossenen Vergleich widerspreche, welcher zudem einen wesentlichen Aspekt des Gestaltungsplans zum Gegenstand hatte. Als Folge ihres Vertrauens haben es die damals noch nicht anwaltlich vertretenen Beschwerdeführer unterlassen, den Gestaltungsplan rechtzeitig auf seine Vereinbarkeit mit dem Vergleich zu prüfen, um Ersteren gegebenenfalls anzufechten (vgl. dazu auch <ref-ruling> E. 1.2.2 S. 376 f. mit Hinweisen). Aus dieser Unterlassung kann deshalb auch nicht auf einen konkludenten Verzicht auf Ansprüche aus dem verwaltungsrechtlichen Vertrag geschlossen werden.
Ein den Vertrauensschutz überwiegendes öffentliches Interesse kann die Gemeinde Falera, die als Vertragspartnerin des Vergleichs und nun auch als Bauherrin auftritt, nicht geltend machen. Schliesslich ist den Beschwerdeführern auch nicht vorzuwerfen, wider Treu und Glauben mit der Ergreifung eines Rechtsmittels zugewartet zu haben, zumal sie gegen die Baubewilligung vom 30. Juni 2009 Beschwerde führten.
2.5 Zusammenfassend ergibt sich, dass sich der angefochtene Entscheid mit dem Grundsatz von Treu und Glauben (<ref-law>) nicht vereinbaren lässt und aufzuheben ist.
Da die Vorinstanz fälschlicherweise vom generellen Vorrang des rechtskräftigen Quartierplans ausging, setzte sie sich nicht mit der Frage auseinander, inwiefern die vorliegend strittige Baubewilligung die Zufahrt zur Parzelle Nr. 395 tatsächlich tangiert bzw. im Widerspruch zum Vergleichsvertrag steht. Sie wird sich in einem neuen Entscheid mit dieser Frage auseinander zu setzen haben. Dabei wird sie berücksichtigen müssen, dass der Vergleichsvertrag vor dem Hintergrund der faktischen Verhältnisse im Zeitpunkt des Vertragsschlusses auszulegen ist (vgl. E. 2.4.2 hiervor und dort zitierte Literatur) und dass die an Parzelle Nr. 395 angrenzende Parzelle Nr. 588 damals noch nicht den Beschwerdeführern gehörte.
3. Die Beschwerde ist teilweise gutzuheissen und die Sache zur neuen Beurteilung im Sinne der Erwägungen an die Vorinstanz zurückzuweisen. Somit ist nicht erforderlich, auf die weiteren Rügen der Beschwerdeführer einzugehen. Im Übrigen wird die Beschwerde abgewiesen.
Gerichtskosten sind bei diesem Verfahrensausgang nicht zu erheben (Art. 66 Abs. 1 und 4 BGG). Die Beschwerdegegnerin hat den im Wesentlichen obsiegenden, anwaltlich vertretenen Beschwerdeführern eine dem Aufwand entsprechende Parteientschädigung zu bezahlen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen und der angefochtene Entscheid aufgehoben. Die Angelegenheit wird zur neuen Beurteilung im Sinne der Erwägungen an das Verwaltungsgericht des Kantons Graubünden zurückgewiesen. Im Übrigen wird die Beschwerde abgewiesen.
2. Es werden keine Gerichtskosten erhoben.
3. Die Beschwerdegegnerin hat die Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 1'500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Verwaltungsgericht des Kantons Graubünden, 5. Kammer, schriftlich mitgeteilt.
Lausanne, 25. Januar 2010
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Dold