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.