Sachverhalt: A. Mit Gesamtbauentscheid vom 10. Oktober 2002 bewilligte der Regierungsstatthalter von Nidau der "Eigentümergemeinschaft H._, p. Adr. Herr G._" auf der Parzelle Tüscherz-Alfermée Gbbl. Nr. 414 den Neubau eines Sechsfamilienhauses mit Büro. Im Rahmen der Umbauarbeiten liess die Bauherrschaft einerseits das frühere Gartenhaus auf der Parzelle Nr. 414 abreissen und an dessen Stelle einen offenen Unterstand erstellen. Andererseits errichtete sie im Garten der Liegenschaft ein Holzdeck, welches ostwärts 2 m in den Bielersee hineinragt. Die Baubewilligung vom 10. Oktober 2002 umfasste diese beiden Bauten nicht. B. Auf Intervention des Regierungsstatthalters hin reichte die Bauherrschaft bei der Einwohnergemeinde Tüscherz-Alfermée einen revidierten Umgebungsgestaltungsplan ein, der u.a. den Unterstand und das Holzdeck zum Gegenstand hatte. Für die letztgenannten Bauten verweigerte das Amt für Gemeinden und Raumordnung des Kantons Bern (AGR) mit Verfügung vom 13. April 2005 die Ausnahmebewilligung nach Art. 24 des Bundesgesetzes über die Raumplanung (RPG; SR 700). Zudem beantragte es in seinem Amtsbericht gleichen Datums, dem Bauvorhaben weder die Zustimmung für Bauten und Anlagen in der Uferschutzzone gemäss Art. 5 Abs. 3 des kantonalen Gesetzes vom 6. Juni 1982 über See- und Flussufer (SFG/BE; BSG 704.1) zu erteilen, noch eine Ausnahme nach Art. 6 Abs. 3 SFG/BE zu gewähren. Mit Verfügung vom 10. Mai 2005 erteilte der Regierungsstatthalter der Bauherrschaft für den bereits erstellten Unterstand und das ebenfalls schon installierte Holzdeck den Bauabschlag und ordnete die vollständige Entfernung der Bauten innert drei Monaten nach Rechtskraft des Entscheides an. Im Übrigen bewilligte er die Umgebungsgestaltung. C. Am 13. Juni 2005 erhoben die A._ AG, X. und Y. B._, X. und Y. C._, D._, die einfache Gesellschaft E._ und F._ sowie G._ als Eigentümer der Parzelle Nr. 414 Beschwerde bei der Bau-, Verkehrs- und Energie direktion des Kantons Bern (BVE) gegen den Bauentscheid und die Wiederherstellungsverfügung. Die BVE wies das Rechtsmittel mit Entscheid vom 12. Dezember 2005 ab. Dagegen gelangten sämtliche Beschwerdeführer ans Verwaltungsgericht des Kantons Bern. Sie ersuchten um Aufhebung der massgeblichen Dispositiv-Ziffern im Entscheid des Regierungsstatthalters vom 10. Mai 2005 und die Bewilligung des Unterstandes sowie des Holzdeckes. Eventualiter sei von der Wiederherstellung abzusehen. Das Verwaltungsgericht wies die Rechtsbegehren mit Urteil vom 17. August 2007 ab. D. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 20. September 2007 beantragen die A._ AG (Beschwerdeführerin 1), X. B._ (Beschwerdeführer 2), X. und Y. C._ (Beschwerdeführer 3), D._ (Beschwerdeführer 4), E._ (Beschwerdeführer 5) und F._ (Beschwerdeführerin 6) sowie G._ (Beschwerdeführer 7) die Aufhebung der Ziff. 4.2 der Verfügung des Regierungsstatthalters vom 10. Mai 2005 und des Urteils des Verwaltungsgerichts des Kantons Bern vom 17. August 2007. Es sei gerichtlich festzustellen, dass der ursprüngliche Zustand im Zusammenhang mit dem Holzdeck auf ihrer Parzelle Gbbl Nr. 414 nicht wiederherzustellen sei. Zugleich stellen die Beschwerdeführer Antrag auf Gewährung der aufschiebenden Wirkung. Nicht zur Angelegenheit geäussert hat sich der Gemeinderat von Tüscherz-Alfermée. Die BVE lässt durch ihr Rechtsamt die Abweisung der Beschwerde beantragen. Das Verwaltungsgericht des Kantons Bern verzichtet auf eine Stellungnahme zum Gesuch um aufschiebende Wirkung und schliesst auf Abweisung der Beschwerde, während das Bundesamt für Raumentwicklung (ARE) von einer Vernehmlassung absieht. Am 18. Oktober 2007 sprach der Präsident der I. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde die aufschiebende Wirkung zu.