Sachverhalt: A. Die E._ AG reichte am 21. Februar 2012 ein Baugesuch ein für den Neubau eines Mehrfamilienhauses mit Einstellhalle auf der Parzelle Gsteig Gbbl. Nr. xxx. Diese befindet sich in der Wohn- und Gewerbezone WG3 der Einwohnergemeinde Gsteig im Gebiet Feutersoey. Gegen das Vorhaben erhoben die Stockwerkeigentümergemeinschaft (STWE) A.A._, B.A._, C.A._ und D.A._ Einsprache. Mit Gesamtentscheid vom 21. August 2012 bewilligte das Regierungsstatthalteramt Obersimmental-Saanen das Bauvorhaben und wies die Einsprache ab. B. Dagegen reichten die genannten Einsprecher am 21. September 2012 Beschwerde bei der Bau-, Verkehrs- und Energiedirektion des Kantons Bern (BVE) ein; diese wies die Beschwerde am 20. Dezember 2012 ab, soweit sie darauf eintrat. C. Gegen den Entscheid der BVE erhoben die Einsprecher am 17. Januar 2013 Beschwerde ans Verwaltungsgericht des Kantons Bern. Das Verfahren wurde bis zu den Grundsatzentscheiden des Bundesgerichts über die Anwendbarkeit von Art. 75b BV vom 22. Mai 2013 sistiert. Der Antrag der E._ AG, das Verfahren bis zum Inkrafttreten der Ausführungsgesetzgebung zu sistieren, wurde abgewiesen. Die dagegen erhobene Beschwerde wies das Bundesgericht am 10. Juni 2014 ab, soweit es darauf eintrat (Urteil 1C_90/2014). Am 23. Juli 2014 stellte die E._ AG den Eventualantrag, die Baubewilligung sei mit der Auflage zu verbinden, die Wohnungen als Erstwohnungen zu nutzen. Am 28. November 2014 führte das Verwaltungsgericht eine öffentliche mündliche Schlussverhandlung mit Parteivorträgen gemäss Art. 6 EMRK durch. Am 22. Januar 2015 hiess es die Beschwerde teilweise gut. Es hob Ziff. 2-4 des Entscheids der BVE vom 20. Dezember 2012 auf und ergänzte den Gesamtentscheid des Regierungsstatthalters vom 21. August 2012 mit folgender Auflage: 6.10 Erstwohnungen Die aufgrund dieser Baubewilligung erstellten Wohnungen müssen als Erstwohnung genutzt werden. Anmerkung im Grundbuch: Das Grundbuchamt Oberland, Dienststelle Frutigen, wird angewiesen, auf dem Grundbuchblatt der Parzelle Gsteig Gbbl. Nr. xxx die Anmerkung "Erstwohnungen" anzubringen. D. Gegen den verwaltungsgerichtlichen Entscheid haben die STWE A.A._, B.A._, C.A._ und D.A._ am 23. Februar 2015 Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht erhoben. Sie beantragen, das angefochtene Urteil sei aufzuheben; der Gesamtbauentscheid des Regierungsstatthalters und der Entscheid der BVE seien für nichtig zu erklären bzw. aufzuheben. Das Baugesuch der E._ AG vom 1. März 2012 sei abzuweisen. Eventualiter sei die Sache zur Neuprüfung und -beurteilung an die Vorinstanz zurückzuweisen. Überdies seien verschiedene Beweise abzunehmen. E. Die E._ AG (Beschwerdegegnerin), die BVE und das Verwaltungsgericht beantragen die Abweisung der Beschwerde. Das Verwaltungsgericht reichte ein Urteil vom 5. Dezember 2014 zur Zonenplanrevision der Gemeinde Gsteig ein. Die Gemeinde Gsteig hat sich nicht vernehmen lassen. Das Bundesamt für Raumentwicklung (ARE) geht davon aus, dass die gerügten Verletzungen von Bundesrecht nicht die Erteilung des Bauabschlags rechtfertigen würden. F. In ihrer Replik halten die Beschwerdeführer an ihrer Beschwerde fest und stellen ergänzende Beweisanträge. G. Mit Verfügung vom 20. März 2015 wurde der Beschwerde aufschiebende Wirkung zuerkannt.