Sachverhalt:
A.
Das Grundstück Nr. 290 im Eigentum von A. und B. C._, Teufen, liegt an einem Südhang und ist mit einem Wohnhaus überbaut, das von unten (Süden) her über einen Fussweg und Treppen ab der Egglistrasse her zugänglich ist. Während rund 100 Jahren konnten die Eigentümer der Parzelle Nr. 290 die Zufahrt von Westen her, über die Parzellen Nrn. 292 und 1937, benutzen, obwohl kein Fahrrecht im Grundbuch eingetragen ist. Mit Schreiben vom 14. August 2013 teilte D._, Eigentümerin der Parzellen Nrn. 292 und 1937, dem Ehepaar C._ mit, dass ihnen ab dem 16. September 2013 das bislang geduldete Befahren und Betreten ihrer Grundstücke verboten sei.
B.
Am 9. September 2013 stellten A. und B. C._ beim Gemeinderat Teufen ein Gesuch um Mitbenutzung der bestehenden Zufahrt auf den Parzellen Nrn. 292 und 1937 gestützt auf Art. 66 des Gesetzes über die Raumplanung und das Baurecht des Kantons Appenzell Ausserrhoden (BauG/AR; bGS 721.1). Der Gemeinderat wies das Gesuch am 16. Oktober 2013 ab, weil die Erschliessung ab der Egglistrasse zumutbar und zweckmässig sei.
C.
Dagegen führten A. und B. C._ Rekurs beim Departement für Bau und Umwelt (DBU). Dieses hiess den Rekurs am 7. Mai 2014 gut und ordnete an, dass die Mitbenutzung der bestehenden Strasse auf der nördlichen Seite der Parzellen Nrn. 292 und 1937 im Grundbuch anzumerken sei.
D.
Dagegen erhob D._ am 10. Juni 2014 Beschwerde bei der verwaltungsgerichtlichen Abteilung des Obergerichts. Dieses führte am 25. März 2015 einen Augenschein durch und hiess gleichentags die Beschwerde gut, soweit darauf einzutreten war.
E.
Gegen den obergerichtlichen Entscheid erhoben A. und B. C._ am 11. September 2015 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht. Sie beantragen, der angefochtene Entscheid sei aufzuheben und derjenige des DBU vom 7. Mai 2014 sei zu bestätigen; eventualiter sei die Angelegenheit zur erneuten Beurteilung an die Vorinstanz zurückzuweisen.
F.
D._ (nachfolgend: die Beschwerdegegnerin) und das Obergericht Appenzell-Ausserrhoden beantragen, die Beschwerde sei abzuweisen. Das DBU schliesst auf Gutheissung der Beschwerde. Der Gemeinderat Teufen hat auf eine Stellungnahme verzichtet.
Im weiteren Schriftenwechsel halten die Parteien an ihren Anträgen fest.
G.
Das Bundesgericht hat die Sache am 3. Mai 2016 in öffentlicher Sitzung beraten und entschieden.

Erwägungen:
1.
Gegen den kantonal letztinstanzlichen Endentscheid über ein öffentlich-rechtliches Nutzungsrecht an einer privaten Zufahrtsstrasse steht grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht offen (Art. 82 lit. a, 86 Abs. 1 lit. d und 90 BGG). Die Beschwerdeführer sind als Gesuchsteller, deren Mitbenutzungsgesuch abgewiesen wurde, zur Beschwerde legitimiert (<ref-law>). Auf die rechtzeitig erhobene Beschwerde (<ref-law>) ist daher einzutreten.
2.
Die Beschwerdeführer rügen zunächst eine Verletzung ihres Anspruchs auf rechtliches Gehör, weil sie keine Gelegenheit erhalten hätten, sich zum Beweisergebnis des obergerichtlichen Augenscheins zu äussern. Dieser habe am Nachmittag des 25. März von 14 bis 16 Uhr stattgefunden. Das Urteil des Obergerichts datiere vom selben Tag. Ein Augenscheinprotokoll sei nicht erstellt oder jedenfalls den Beschwerdeführern nicht zugestellt worden. Erst in der schriftlichen Urteilsbegründung hätten sie Kenntnis davon erhalten, was das Obergericht am Augenschein konkret festgestellt habe; dies obwohl sie mit Schreiben vom 20. Oktober 2014 ausdrücklich festgehalten hätten, sie würden zwar auf die Durchführung einer Hauptverhandlung, nicht aber auf eine mündliche Beweisverhandlung verzichten.
2.1. Die Vorinstanz macht in ihrer Vernehmlassung geltend, der Rechtsvertreter der Beschwerdeführer sei regelmässig vor Obergericht tätig, weshalb ihm bekannt gewesen sei, dass das Gericht an seinen Augenscheinen immer vollzählig anwesend sei und dann gleichentags entscheide. Bekannt sei ihm ebenfalls, dass es seine Feststellungen stets durch den Gerichtsschreiber fotografisch festhalten lasse und die Fotodokumentation im Fall der Anfechtung direkt ans Bundesgericht leite. Die Bilder dokumentierten, was die Parteien dem Gericht an Ort und Stelle gezeigt hätten und der Gerichtsschreiber vor ihren Augen fotografiert habe. Die wesentlichen Feststellungen des Augenscheins wie auch die dort erstmals erhobenen Rügen der Parteien seien, soweit entscheiderheblich, zusätzlich auch im angefochtenen Urteil festgehalten. Weil die Beschwerdeführer auf eine mündliche Hauptverhandlung verzichtet hätten, habe das Obergericht nach Treu und Glauben unmittelbar im Anschluss an den Augenschein sein Urteil fällen können.
2.2. Gemäss <ref-law> haben die Parteien Anspruch auf rechtliches Gehör. Dieses 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 unter anderem das Recht der Betroffenen, an der Erhebung wesentlicher Beweise mitzuwirken oder sich zumindest zum Beweisergebnis zu äussern, wenn dieses geeignet ist, den Entscheid zu beeinflussen (<ref-ruling> E. 2.1 S. 127; <ref-ruling> E. 2.2 S. 190; je mit Hinweisen).
Aus dem Anspruch auf rechtliches Gehör wird zudem eine allgemeine Aktenführungspflicht der Behörden abgeleitet, als Gegenstück zum Akteneinsichts- und Beweisführungsrecht der Parteien (Gerold Steinmann, in: St. Galler BV-Kommentar, 3. Aufl. 2014, N. 55 zu <ref-law>). Dazu gehört die Pflicht zur Protokollierung entscheidrelevanter Abklärungen, Einvernahmen und Verhandlungen im Rechtsmittelverfahren (<ref-ruling> E. 4.2 S. 477 f.; <ref-ruling> E. 4a und b S. 390 f.). Das Protokoll dient einerseits den Richtern und dem Gerichtsschreiber als Gedächtnisstütze und soll es ihnen ermöglichen, die Ausführungen der Parteien tatsächlich zur Kenntnis zu nehmen und pflichtgemäss zu würdigen; andererseits soll es Auskunft über die Einhaltung der Verfahrensvorschriften geben und die Rechtsmittelinstanzen in die Lage versetzen, den angefochtenen Entscheid zu überprüfen (Urteil 1C_82/2008 vom 28. Mai 2008, in <ref-ruling> nicht veröffentlichte E. 5.2; Urteil 2A.450/1999 vom 14. Januar 2000 E. 3b/aa).
Die neuen Prozessordnungen des Bundes schreiben ein schriftliches Augenscheinprotokoll vor, gegebenenfalls ergänzt mit Plänen, Zeichnungen, fotografischen und andern technischen Mitteln (<ref-law>; <ref-law>). In Botschaft und Kommentierung zu <ref-law> wird betont, dass nur die im Protokoll dokumentierten Ergebnisse des Augenscheins im Urteil verwertet werden dürften (Botschaft zur ZPO vom 28. Juni 2006, BBl 2006 7324; ALFRED BÜHLER, in: Berner Kommentar zur ZPO, Bd. II, 2012, N. 3 zu Art. 182; WEIBEL/WALZ in: Sutter-Somm et al., ZPO-Kommentar, 3. Aufl. 2016, N. 1 zu Art. 182; ANNETTE DOLGE, in: Basler Kommentar zur ZPO, 2. Aufl. 2013, N. 2 zu Art. 182). Das Augenscheinprotokoll kann als Teil der Akten von den Parteien eingesehen werden (<ref-law>); in der Regel wird es ihnen vom Gericht zugestellt (DENIS TAPPY, in: CPC, Code de procédure civile commenté, 2011, N. 12 zu <ref-law>; CHRISTOPH LEUENBERGER in: Sutter-Somm, ZPO-Kommentar, N. 5 zu <ref-law>). Damit werden die Parteien insbesondere in die Lage versetzt, allfällige Berichtigungsgesuche zu stellen (<ref-law>). Im Strafprozess gelten die strengen und i.d.R. zwingenden Protokollierungsregeln gemäss <ref-law> (vgl. Urteil 6B_492/2012 vom 22. Februar 2013 E. 1.4).
2.3. Auch im Verwaltungsjustizverfahren ergibt sich aus dem Anspruch der Verfahrensbeteiligten auf rechtliches Gehör eine Protokollierungspflicht für Augenscheine (<ref-ruling> E. 4.2 S. 478 mit Hinweisen). Dies entspricht auch der einhelligen Auffassung der Literatur (KÖLZ/HÄNER/BERTSCHI, Verwaltungsverfahren und Verwaltungsrechtspflege des Bundes, 3. Aufl., Rz. 497; ATTILIO R. GADOLA, Das verwaltungsinterne Beschwerdeverfahren, Diss. Zürich 1991, S. 409; PIERRE Moor/Etienne Poltier, Droit administratif, Bd. II, 3. Aufl. 2011, S. 298; Benoît Bovay, Procédure administrative, 2. Aufl. 2015, S. 283; MOSER/BEUSCH/KNEUBÜHLER, Prozessieren vor dem Bundesverwaltungsgericht, 2. Aufl. Rz. 3.139; CHRISTOPH AUER, Kommentar VwVG, 2008, Art. 12 N. 52 f.; KRAUSKOPF/EMMENEGGER/BABEY, in: Waldmann/Weissenberger, Praxiskommentar VwVG, 2. Aufl. 2016, N. 46 zu Art. 12; WALDMANN/OESCHGER, Praxiskommentar VwVG, N. 41 Art. 26; MERKLI/AESCHLIMANN/HERZOG, Kommentar zum Gesetz über die Verwaltungsrechtspflege im Kanton Bern, Bern 1997, N. 33 zu Art. 19 Rz. 33 und N. 1 zu Art. 123 VRG/BE; KASPAR PLÜSS, in: Alain Griffel [Hrsg.], Kommentar VRG, 3. Aufl. 2014, N. 88 zu § 7 VRG/ZH).
Grundsätzlich ist zu verlangen, dass die Ergebnisse des Augenscheins, insbesondere die vom Gericht vor Ort gemachten Feststellungen und Wahrnehmungen, ihrem wesentlichen Inhalt nach schriftlich protokolliert werden, allenfalls ergänzt mit Fotos, Plänen, etc. Den Parteien muss vor Entscheidfällung die Möglichkeit gegeben werden, davon Kenntnis zu nehmen und sich dazu zu äussern, insbesondere allfällige Berichtigungen zu verlangen. Im bundesgerichtlichen Verfahren lässt sich dies nicht nachholen: Gemäss <ref-law> können die Parteien nur noch geltend machen, der Sachverhalt sei offensichtlich unrichtig oder unvollständig festgestellt worden. Das Protokoll ist ihnen daher i.d.R. mit Fristansetzung zuzustellen (AUER, a.a.O., N. 53 zu <ref-law>). Bei diesem Vorgehen wird gewährleistet, dass das Protokoll eine verlässliche Grundlage für die Entscheidfällung des Gerichts und für ein späteres Rechtsmittelverfahren darstellt und den Parteien das rechtliche Gehör vollumfänglich gewährt wurde.
2.4. In seiner bisherigen Rechtsprechung zum Verwaltungsgerichtsverfahren hat das Bundesgericht (vorbehältlich strengerer Anforderungen des kantonalen Rechts) gewisse Abweichungen von den oben dargestellten Grundsätzen toleriert, insbesondere wenn im Anschluss an den Augenschein noch eine Parteiverhandlung durchgeführt wurde und die Ergebnisse des Augenscheins und die wesentlichen Äusserungen der Parteien in den Urteilserwägungen hinlänglich wiedergegeben und gewürdigt wurden (<ref-ruling> E. 2a S. 75; <ref-ruling> E. 2 S. 217; Urteile 1C_193/2011 vom 24. August 2011 E. 2.3; 1C_372/2010 vom 11. Februar 2011 E. 7; offengelassen in Urteil 1C_82/2008 vom 28. Mai 2008, in <ref-ruling> nicht publizierte E. 5.2; 1C_430/2008 vom 16. April 2009 E. 2.3.2; 1C_134/2007 vom 24. Januar 2008 E. 3.2-3.4; kritisch dazu WALDMANN/OESCHGER, a.a.O., N. 41 zu Art. 26; K ÖLZ/HÄNER/BERTSCHI, a.a.O. Rz. 497). Ob und inwieweit an diesen Ausnahmen in sachverhaltlich einfach gelagerten Fällen festzuhalten ist, braucht vorliegend nicht weiter erörtert zu werden, weil das Vorgehen des Obergerichts jedenfalls - wie aus dem Folgenden hervorgeht - das rechtliche Gehör der Beschwerdeführer verletzt hat. Auch weiterhin besteht jedenfalls die Möglichkeit, das Protokoll den Parteien bereits am Augenschein zur Stellungnahme zu unterbreiten; diesen steht es ausserdem frei, auf die Erstellung eines Augenscheinprotokolls zu verzichten (Urteil 1C_82/2008 vom 28. Mai 2008, in <ref-ruling> nicht publizierte E. 5.2).
2.5. Am Augenschein vom 25. März 2015 wurden verschiedene Sachverhaltsfeststellungen getroffen, die für den Entscheid erheblich waren. Eine Parteiverhandlung wurde im Anschluss an den Augenschein nicht durchgeführt; in der Urteilsbegründung finden sich auch keine Äusserungen der Parteien zum Ergebnis des Augenscheins.
Hinzu kommt, dass das Obergericht nachträglich eine umfangreiche, aussagekräftige Fotodokumentation erstellt und direkt dem Bundesgericht übermittelt hat, mit zahlreichen Fotos, Kommentaren, Massangaben und Hervorhebungen mit roten oder gelben Pfeilen. Auch wenn die Fotos vor den Augen der Parteien gemacht wurden, wie das Obergericht vorbringt, ersetzt dies nicht die Möglichkeit, sich zu den fertigen Bildern (Bildausschnitt, Belichtung, Bearbeitung, Standort des Fotografen etc.) und damit möglicherweise verbundenen falschen Eindrücken vor Urteilsfällung zu äussern; gleiches gilt für die Begleitkommentare mit Distanzangaben. Nur unter dieser Voraussetzung ist der Anspruch der Parteien auf Mitwirkung am Beweisverfahren gewährleistet und kann die Dokumentation dem Urteil oder einem späteren Rechtsmittelverfahren zugrundegelegt werden (so schon <ref-ruling> E. 4.5 S. 480 f. zu Tonaufzeichnungen).
Vorliegend wurde den Beschwerdeführern die Fotodokumentation erst im bundesgerichtlichen Verfahren als Beilage zur Vernehmlassung des Obergerichts zur Kenntnis gebracht. Dieses macht selbst nicht geltend, dass die Dokumentation schon vor Beschwerdeerhebung in den Akten lag und hätte eingesehen werden können. Insofern konnten die Beschwerdeführer sich weder vor Obergericht, noch in ihrer Beschwerdeschrift ans Bundesgericht dazu äussern, sondern erst in ihrer Replik vom 18. Dezember 2015.
2.6. Entgegen der Auffassung des Obergerichts kann auch nicht von einem Verzicht der Parteien ausgegangen werden: Die Beschwerdeführer hatten zwar mit Eingabe vom 20. Oktober 2014 auf eine mündliche Hauptverhandlung verzichtet, hielten aber (wie auch die Beschwerdegegnerin) ausdrücklich an einer mündlichen Beweisverhandlung fest. Unter diesen Umständen durfte das Obergericht nach Treu und Glauben nicht ohne Nachfrage davon ausgehen, die Parteien seien mit der sofortigen Urteilsfällung und einer nachträglichen Fotodokumentation einverstanden, auch wenn dies der bisherigen Praxis entsprach.
2.7. Nach dem Gesagten ist eine Verletzung des rechtlichen Gehörs der Beschwerdeführer zu bejahen. Dieser Mangel kann wegen der beschränkten Kognition des Bundesgerichts nicht geheilt werden (Art. 97 und 105 BGG). Der angefochtene Entscheid ist daher aufzuheben und die Sache an das Obergericht zurückzuweisen. Dieses muss den Parteien Gelegenheit einräumen, zum Ergebnis des Augenscheins, inklusive zur Fotodokumentation, Stellung zu nehmen, bevor es erneut entscheidet.
3.
Bei diesem Ausgang des Verfahrens obsiegen die Beschwerdeführer. Die private Beschwerdegegnerin wird damit kosten- und entschädigungspflichtig (Art. 66 und 68 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen und der Entscheid der 4. Abteilung des Obergerichts Appenzell Ausserrhoden vom 25. März 2015 aufgehoben. Die Sache wird zu neuer Beurteilung im Sinne der Erwägungen an das Obergericht zurückgewiesen.
2.
Die Gerichtskosten von Fr. 3'000.-- werden der Beschwerdegegnerin auferlegt.
3.
Die Beschwerdegegnerin hat die Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien, dem Gemeinderat Teufen, dem Departement Bau und Umwelt und dem Obergericht Appenzell Ausserrhoden 4. Abteilung schriftlich mitgeteilt.
Lausanne, 3. Mai 2016
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Die Gerichtsschreiberin: Gerber