Sachverhalt: A. Die Biomasse Jungfrau AG reichte am 12. Mai 2012 bei der Einwohnergemeinde Interlaken ein Baugesuch ein für eine Biogasanlage zur (Nass-) Vergärung von organischen Abfällen und Hofdünger zwecks Produktion von Biomethan auf der in der Zone für öffentliche Nutzung g (Kehrichtumladestation) liegenden und der Einwohnergemeinde Interlaken gehörenden Parzelle Interlaken Gbbl. Nr. 1093. Dagegen erhoben unter anderem A.A._ und B.A._ als Gesamteigentümer der mehr als 300 m entfernten Parzelle Interlaken Gbbl. Nr. xxx sowie letzterer überdies als Eigentümer der rund 350 m entfernten Liegenschaft Interlaken Gbbl. Nr. yyyy Einsprache. Mit Gesamtbauentscheid vom 22. Mai 2012 erteilte das Regierungsstatthalteramt Interlaken-Oberhasli für das Bauprojekt die Baubewilligung, die Gewässerschutzbewilligung und die Anlagegenehmigung. B. Gegen diesen Gesamtbauentscheid reichten A.A._ und B.A._ am 21. Juni 2012 Beschwerde bei der Bau-, Verkehrs- und Energiedirektion des Kantons Bern ein. Diese wies die Beschwerde am 5. November 2012 ab, soweit sie darauf eintrat. C. Mit Urteil vom 22. März 2013 wies der Einzelrichter am Verwaltungsgericht des Kantons Bern eine dagegen erhobene Beschwerde von A.A._ und B.A._ ab, soweit er darauf eintrat. D. A.A._ und B.A._ führen Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht mit dem Antrag, das Urteil des Verwaltungsgerichts sowie den Gesamtbauentscheid aufzuheben und dem Bauvorhaben den Bauabschlag zu erteilen. E. Die Biomasse Jungfrau AG und das Verwaltungsgericht des Kantons Bern schliessen auf Abweisung der Beschwerde. Die Einwohnergemeinde Interlaken äusserte sich ablehnend zur Beschwerde, ohne einen förmlichen Antrag zu stellen. Die Bau-, Verkehrs- und Energiedirektion des Kantons Bern hat auf eine Stellungnahme verzichtet. F. In Replik und Duplik halten A.A._ und B.A._ einerseits sowie die Biomasse Jungfrau AG andererseits im Wesentlichen an ihren Standpunkten fest.