Sachverhalt:
A. C._ ist Eigentümerin der Parzelle Nr. 276 im Dorfkern von Bever. Der östliche Teil der Liegenschaft ist mit einem Wohnhaus überbaut, auf dem westlichen Teil befindet sich ein Innenhof, der durch einen Holzzaun mit Einfahrtstor nach Süden gegen die Via Chà Suot abgegrenzt ist. Im Norden grenzt die Parzelle Nr. 276 an die Nr. 275 von A._ und B._. Diese ist mit einem Wohnhaus überbaut, wobei der östliche Teil der Südfassade mit dem Wohnhaus auf der Parzelle Nr. 276 zusammengebaut ist, während der westliche Teil der Südfassade den (nördlichen) Abschluss des Innenhofs der Parzelle Nr. 276 bildet. Die Parzelle Nr. 275 verfügt über einen Zugang über diesen Innenhof zur Via Chà Suot; dieser Teil der Parzelle Nr. 276 ist mit den entsprechenden Dienstbarkeiten - dem "unbeschränkten Fuss- und Fahrwegrecht sowie dem Recht des Aufstellens von Fahrzeugen und Handwagen aller Art" sowie dem "Recht, sich auf dem ganzen Areal der belasteten Parzelle aufzuhalten" - zugunsten der Parzelle Nr. 275 belastet.
Am 4. April 2008 reichte C._ ein Baugesuch ein für die Verschiebung des bestehenden Einfahrtstores in den Innenhof von der Mitte an die Westgrenze der Liegenschaft. A._ und B._ erhoben Einsprache mit dem Antrag, das Baugesuch abzulehnen. Nach den von der Gemeinde eingeholten Erklärungen der Gesuchstellerin sollte mit der Verschiebung des Tores an den Parzellenrand eine rationellere Nutzung des Innenhofs (Zufahrt, Parkierung) unter Wahrung der privatrechtlichen Dienstbarkeitsvorgaben sowie die Schaffung eines zusätzlichen Aussenparkplatzes zwischen Zaun und Strasse erreicht werden. Nachdem C._ noch einen Situationsplan mit einer möglichen Parkordnung eingereicht hatte, genehmigte die Gemeinde Bever das Baugesuch und wies die Einsprache ab.
A._ und B._ fochten die Baubewilligung beim Verwaltungsgericht des Kantons Graubünden an, welches die Beschwerde am 17. Februar 2009 abwies.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragen A._ und B._, das verwaltungsgerichtliche Urteil sowie Ziff. III 1.-3. des Einsprache- und Baubewilligungsentscheids der Gemeinde Bever vom 21. Mai 2008 aufzuheben oder eventuell die Sache an die Gemeinde Bever zur Neubeurteilung oder subeventuell an das Verwaltungsgericht zur Beweisergänzung und Neubeurteilung zurückzuweisen. Die Sache sei dem Verwaltungsgericht zur Neubeurteilung der Kosten und Entschädigungsregelung zurückzuweisen. In verfahrensrechtlicher Hinsicht beantragen die Beschwerdeführer, der Beschwerde aufschiebende Wirkung zuzuerkennen und der Beschwerdegegnerin zu verbieten, das umstrittene Bauvorhaben zu realisieren. Ausserdem ersuchen sie, einen Augenschein durchzuführen.
C. Mit Verfügung vom 13. Juli 2009 erkannte der Präsident der I. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde aufschiebende Wirkung zu.
D. Die Gemeinde Bever verzichtet auf Vernehmlassung. Das Verwaltungsgericht beantragt, die Beschwerde abzuweisen. C._ beantragt, auf die Beschwerde nicht einzutreten oder sie eventuell abzuweisen.
A._ und B._ halten in der Replik an der Beschwerde fest. Die Gemeinde Bever teilt mit, dass A._ und B._ die Liegenschaft Nr. 275 per 1. Oktober 2009 an D._ verkauft haben; im Übrigen verzichtet sie auf Replik.
C._ hält in der Duplik an ihrem Standpunkt fest.
A._ und B._ bestätigen, die Liegenschaft Nr. 275 an D._ verkauft zu haben, und erklären, an der Beschwerde festzuhalten und den Streit in Prozessstandsschaft für die Erwerberin, welche ihr Interesse an der Gutheissung der Beschwerde erklärt habe, weiterzuführen.

Erwägungen:
1. Angefochten ist ein kantonal letztinstanzlicher Entscheid über eine Baubewilligung, gegen den die Beschwerde in öffentlich-rechtlichen Angelegenheiten grundsätzlich offen steht (<ref-law>).
1.1 Formell nicht Gegenstand des Verfahrens war die bewilligungspflichtige Beseitigung des Baumes, der sich direkt hinter der neuen Einfahrt befindet und der für die Realisierung des Bauvorhabens zwingend entfernt werden muss. Es fragt sich daher, ob der angefochtene Entscheid einen verfahrensabschliessenden Endentscheid im Sinn von <ref-law> darstellt oder einen Zwischenentscheid im Sinn von <ref-law>. Die Gemeinde Bever hat der Beschwerdegegnerin die Bewilligung für die Fällung des Baumes in Aussicht gestellt. Das Verwaltungsgericht hat dies materiell geprüft und die Gemeinde angewiesen, die Beseitigung des Baumes zu bewilligen (E. d S. 8). Der angefochtene Entscheid erweist sich somit als verfahrensabschliessender Endentscheid, dem Eintreten steht unter diesem Gesichtspunkt nichts entgegen.
1.2 Die Beschwerdeführer sind im kantonalen Verfahren unterlegen und damit formell beschwert. Sie sind unmittelbare Nachbarn und zudem berechtigt, das streitbetroffene Einfahrtstor zu benutzen, womit sie über eine spezifische Beziehungsnähe zur Streitsache verfügen. Da nach ihrem Standpunkt die Verschiebung des Einfahrtstores die Zufahrt zu ihrem Haus erschwert, könnten sie aus der Gutheissung ihrer Beschwerde einen praktischen Nutzen ziehen (<ref-ruling> E. 1.3). Sie sind damit beschwerdebefugt. Der Umstand, dass sie ihre Liegenschaft nach der Rechtshängigkeit des bundesgerichtlichen Verfahrens verkauft haben, ändert nichts an ihrer Legitimation in der Sache (<ref-law> i.V.m. <ref-law>). Das Verfahren ist somit auf ihren Namen fortzusetzen (<ref-ruling> E. 1b S. 223 mit Hinweisen; Urteil des Bundesgerichts 1C_32/2007 vom 18. Oktober 2007 E. 1.1).
1.3 Die von den Beschwerdeführern vorgebrachten Rügen - der angefochtene Entscheid verstosse gegen Bundesrecht bzw. wende kantonales Recht in bundesrechtswidriger Weise an - sind zulässig (<ref-law>; <ref-ruling> E. 1.2.1). Auf die Beschwerde ist somit einzutreten. Dies gilt allerdings nur, soweit die Beschwerdebegründung den gesetzlichen Begründungsanforderungen von <ref-law> bzw. <ref-law> für Verfassungsrügen genügt (<ref-ruling> E. 2.1; <ref-ruling> E. 3.2).
1.4 Abzuweisen ist der Antrag auf Durchführung eines Augenscheins, da sich der rechtserhebliche Sachverhalt mit ausreichender Klarheit aus den Akten ergibt.
2. Die Beschwerdeführer rügen, das Verwaltungsgericht habe ihr rechtliches Gehörs verletzt, indem es nach der Durchführung des Augenscheins mehrere Richter ausgewechselt habe.
Das Verwaltungsgericht erklärt dazu, die beiden nebenamtlichen Verwaltungsrichter, die am Augenschein teilgenommen hätten, seien per 2009 durch vollamtliche Richter ersetzt worden. Allerdings hätten der amtierende Präsident und der Aktuar am Augenschein teilgenommen und entsprechend darüber berichten können.
Die Beschwerdeführer machen nicht geltend, dass ein Augenschein nicht auch durch eine Delegation des Gerichts durchgeführt werden kann. Sodann wurde über den Augenschein ein Protokoll verfasst. Unter diesen Umständen hat das Verwaltungsgericht das rechtliche Gehör der Beschwerdeführer nicht verletzt, indem es das Urteil unter der Mitwirkung von Richtern fällte, die am Augenschein nicht teilgenommen hatten.
3. Die Beschwerdeführer rügen eine Verletzung bzw. sinngemäss eine willkürliche Anwendung von Art. 92 und Art. 125 des kantonalen Raumplanungsgesetzes vom 6. Dezember 2004 (KRG) und von Art. 45 der kantonalen Raumplanungsverordnung vom 24. Mai 2005 (KRVO). Auf die Rüge, das Verwaltungsgericht habe Art. 125 KRG verletzt, ist nicht einzutreten, da es diese Bestimmung nicht gibt. Im Übrigen machen die Beschwerdeführer in diesem Zusammenhang geltend, es sei für die Parkplätze kein ordentliches Baubewilligungsverfahren durchgeführt worden. Sie gehen davon aus, dass die Errichtung der umstrittenen Parkplätze baubewilligungspflichtig ist. Dafür spricht auf den ersten Blick die in Dispositiv-Ziff. 2 der kommunalen Baubewilligung gemachte Auflage, wonach die Bauherrschaft verpflichtet wird, die Parkplätze Nrn. 1-5 im Innenhof wie auf dem Plan vom 21. Mai 2008 anzuordnen und sich an die Parkordnung zu halten.
Mit dem Baugesuch vom 4. April bzw. der Planbeilage vom 2. April 2008 wurde (nur) um die Verschiebung der bestehenden Hofeinfahrt ersucht. Die von der Beschwerdegegnerin eingereichte Planunterlage vom 20./21.Mai 2008 bildete die Antwort auf die Aufforderung des Baukommissionspräsidenten um Darlegung der Gründe für die Verschiebung des Einfahrtstores. Es ist darin kein Baugesuch für die Erstellung von Parkplätzen zu erblicken. Im Übrigen ergibt sich weder aus der Baubewilligung noch aus den Ausführungen der Beschwerdeführer, dass das Parkieren auf der Parzelle Nr. 276 bewilligungspflichtig ist bzw. inwiefern es sich bei den auf dem Plan eingezeichneten Parkplätzen um eine bewilligungspflichtige Anlage handeln soll. Die erwähnte Auflage hinsichtlich der Parkordnung kann namentlich nicht bedeuten, dass die Beschwerdegegnerin verpflichtet wäre, die im Plan eingezeichneten Parkplätze zu erstellen, wie das z.B. etwa bei sogenannten Pflichtparkplätzen der Fall wäre. Sie kann nur bedeuten, dass mindestens die nicht für das Parkieren vorgesehene Fläche des Hofraumes freigehalten werden muss, nicht aber, dass die Beschwerdegegnerin ungeachtet allfälliger privatrechtlicher Ansprüche der Beschwerdeführer ermächtigt wäre, auf den im Plan vorgesehenen Parkplätzen Fahrzeuge abzustellen. Ob das diesen zustehende Fahrwegrecht auch den Anspruch umfasst, Fahrzeuge jeglicher Art auf dem fahrwegbelasteten Hofraum zu wenden und - gegebenenfalls - in welchem Umfang der Hofraum dafür freigehalten werden müsste, ist eine im Streifall vom Zivilrichter zu beurteilende Frage. Die Rüge, es sei in Bezug auf die in der Planunterlage vorgesehenen Parkplätze kein ordentliches Baubewilligungsverfahren durchgeführt worden, ist unbegründet.
4. Die Beschwerdeführer haben vor Verwaltungsgericht gerügt, ihr rechtliches Gehör sei verletzt worden, weil sie sich nicht zu den von der Beschwerdegegnerin nachträglich eingereichten Planunterlagen hätten äussern können. Das Verwaltungsgericht hat diese Rüge zwar anerkannt, jedoch ausgeführt, die Gehörsverletzung sei im verwaltungsgerichtlichen Verfahren geheilt worden. Die Beschwerdeführer stellen dies nicht in Frage und kommen damit ihrer Begründungspflicht nicht nach. Auf die Gehörsverweigerungsrüge ist nicht einzutreten.
5. 5.1 Die Beschwerdeführer rügen, die Anordnung bzw. Bemessung der Parkplätze im Hofraum entspreche nicht den anerkannten Regeln der Baukunde und erschwere die Ausübung ihres Fahrwegrechts erheblich. Sie gehen dabei von der unzutreffenden Auffassung aus, dass die Parkplätze mit dem angefochtenen Entscheid bewilligt und von der Beschwerdegegnerin ohne Einschränkungen benützt werden dürfen. Das ist indessen nicht der Fall, wie sich aus den obenstehenden Ausführungen ergibt (E. 3). Die Rüge ist damit unbegründet.
5.2 Die Beschwerdeführer rügen indessen auch, die bewilligte Ausfahrt in die Strasse entspreche nicht den einschlägigen VSS-Normen und verletze damit Art. 42 Abs. 1 des Baugesetzes von Bever vom 14. Juni 2005 (BauG), welcher vorschreibe, dass Ausfahrten von Garagen und Abstellplätzen den einschlägigen VSS-Normen zu genügen hätten. Die normwidrige Ein-/Ausfahrt gefährde zudem die Verkehrssicherheit.
Das Bundesgericht prüft die Anwendung kommunalen und kantonalen Rechts nur auf Willkür, und die Beschwerdeführer begründen nicht in einer den gesetzlichen Anforderungen entsprechenden Weise, inwiefern die Bewilligung der neuen Ausfahrt auf einer unhaltbaren Anwendung der einschlägigen Bestimmungen des kommunalen Baugesetzes beruhen soll. Das Argument, die geplante Ein- bzw. Ausfahrt entspreche nicht den einschlägigen VSS-Normen, genügt schon deswegen nicht für den Nachweis von Willkür, weil nach Art. 42 Abs. 5 BauG die Baubehörde in der Dorfkern- und Dorfzone unter Abwägung der verschiedenen öffentlichen Interessen von den Vorschriften dieses Artikels - also namentlich auch von Abs. 1 - Ausnahmen bewilligen kann. Ob die von den Beschwerdeführern ebenfalls angerufene Vorschrift, das Einfahrtstor müsse nach Art. 42 Abs. 3 BauG einen Abstand von 5 m zur Strasse einhalten, überhaupt einschlägig ist - sie bezieht sich explizit nur auf Einstellhallen und Garagen - kann offen bleiben, da nach Art. 42 Abs. 5 BauG jedenfalls auch davon Ausnahmen zulässig sind. Keiner weiteren Ausführungen bedarf, dass historische Dorfkerne nicht auf die Bedürfnisse des motorisierten Individualverkehrs ausgerichtet sind und dessen in den VSS-Normen festgelegten Anforderungen häufig nicht entsprechen. Das dürfte nach den Ausführungen der Beschwerdeführer auch auf die umstrittene Ausfahrt zutreffen. Entscheidend ist indessen, dass sich nach der plausiblen Beurteilung der Gemeindevertreter am verwaltungsgerichtlichen Augenschein, der sich das Verwaltungsgericht anschloss, die Verkehrsverhältnisse durch die Verschiebung der Toreinfahrt nicht massgeblich veränderten bzw. verschlechterten und die Ein- und Ausfahrt in die Via Chà Suot nach dem neuen Projekt problemlos möglich sein wird und auch unter dem Gesichtspunkt der Verkehrssicherheit (Art. 38 Abs. 1 BauG) vertretbar ist. Dass diese Einschätzung unhaltbar sein soll, weisen die Beschwerdeführer nicht nach, und das ist auch nicht ersichtlich. Unter diesen Umständen ist die Baubewilligung für die Verschiebung des Einfahrtstores auch unter diesem Aspekt verfassungsrechtlich nicht zu beanstanden.
6. Art. 89 Abs. 3 KRG bestimmt, dass Baugesuche, bei denen die Bauherrschaft nicht Eigentümerin des Baugrundstücks ist, auch von der Grundeigentümerin zu unterzeichnen sind. Die Beschwerdeführer machen geltend, das Baugesuch der Beschwerdegegnerin hätte nach dieser Vorschrift auch von ihnen mitunterzeichnet werden müssen. Der Einwand ist schlechterdings nicht nachvollziehbar, sind doch die Beschwerdeführer unbestrittenermassen nicht Eigentümer des Baugrundstücks.
7. Die Beschwerdeführer werfen dem Verwaltungsgericht vor, ihr rechtliches Gehör verletzt zu haben, indem es ihnen die Kostennote der gegnerischen Parteivertreterin nicht zur Stellungsnahme zugestellt habe. Die Rüge ist insofern begründet, als ihnen als Teilaspekt des fairen Verfahrens nach <ref-law> bzw. Art. 6 Ziff. 1 EMRK das Recht zusteht, zu allen dem Gericht eingereichten Akten Stellung zu nehmen (<ref-ruling> E. 4.3-4.6), unabhängig davon, ob sie geeignet sind, den Verfahrensausgang zu beeinflussen. Dies gilt nach der Rechtsprechung auch für Kostennoten (Entscheide des Bundesgerichts 1C_147/2008 vom 11. November 2008 E. 3 und 1C_40/2008 vom 5. Mai 2008 E. 4).
Die Beschwerdeführer machen geltend, die fragliche Honorarnote vom Verwaltungsgericht erst nach zweimaliger Aufforderung, während der für die Beschwerde ans Bundesgericht laufenden Rechtsmittelfrist erhalten zu haben. Davon ist auszugehen, da das Verwaltungsgericht dies in der Vernehmlassung nicht bestreitet. Allerdings findet sich Rechtsanwalt Stefan Metzger auf der Verteilerliste des Begleitschreibens der fraglichen Kostennote, es liegt somit nahe, dass ihm diese in Kopie zugestellt wurde, was anwaltlicher Usanz entspricht. Ein Beweis, dass er die fragliche Kostennote vom Gegenanwalt direkt zugestellt erhalten hat, findet sich in den Akten indessen, soweit ersichtlich, nicht. Immerhin steht fest, dass sie vor Ablauf der Rechtsmittelfrist der Beschwerde ans Bundesgericht davon Kenntnis erhielten, die Beschwerdeführer hatten somit Gelegenheit und Anlass, die aus ihrer Sicht offenbar überhöhten Kostennote zu kritisieren und dem Bundesgericht die Senkung der vom Verwaltungsgericht zugesprochenen Parteientschädigung zu beantragen. Da sie keine kritischen Einwände gegen die Kostennote erheben, liefe die Aufhebung des Verwaltungsgerichtsentscheids im Kostenpunkt und eine entsprechende Rückweisung der Sache auf einen Leerlauf hinaus, weshalb die Beschwerde auch in diesem Punkt abzuweisen ist.
8. Die Beschwerde ist somit abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens werden die Beschwerdeführer kostenpflichtig (<ref-law>), und sie haben der Beschwerdegegnerin zudem eine angemessene Parteientschädigung zu bezahlen (Art. 68 Abs. 1 und 2 BGG).

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 Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 4'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, der Gemeinde Bever und dem Verwaltungsgericht des Kantons Graubünden, 5. Kammer, schriftlich mitgeteilt.
Lausanne, 7. Mai 2010
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Störi