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.

Erwägungen:
1. 1.1 Das angefochtene Urteil des Verwaltungsgerichts, ein Endentscheid (<ref-law>) einer letzten kantonalen Instanz (<ref-law>), betrifft die Bewilligungsfähigkeit einer Baute in der kantonalen Uferschutzzone. Gestützt auf <ref-law> beurteilt das Bundesgericht Beschwerden gegen Entscheide in Angelegenheiten des öffentlichen Rechts. Dieses Rechtsmittel steht auch auf dem Gebiet des Raumplanungs- und Baurechts zur Verfügung. Das Bundesgerichtsgesetz enthält dazu keinen Ausschlussgrund. Gemäss Art. 34 Abs. 1 RPG in der Fassung nach Ziff. 64 des Anhangs zum Bundesgesetz vom 17. Juni 2005 über das Bundesverwaltungsgericht (VGG; SR 173.32; vgl. AS 2006, 2261) gelten für die Rechtsmittel an die Bundesbehörden die allgemeinen Bestimmungen über die Bundesrechtspflege. An der Zulässigkeit der Beschwerde in öffentlich-rechtlichen Angelegenheiten ändert nichts, wenn - wie hier - lediglich die Bundesverfassungsmässigkeit der Handhabung von kantonalem bzw. kommunalem Baurecht im Streit liegt.
Die Beschwerdeführer fechten den Bauabschlag in Bezug auf das Holzdeck und die vom Verwaltungsgericht geschützte Wiederherstellungsverfügung an. Dazu sind sie legitimiert (<ref-law>). Die Beschwerde wurde rechtzeitig (<ref-law>) erhoben. Insoweit sind die Eintretensvoraussetzungen erfüllt.
1.2 Unzulässig ist der Antrag der Beschwerdeführer, auch Dispositiv-Ziff. 4.2 der regierungsstatthalterlichen Verfügung vom 10. Mai 2005 aufzuheben. Diese Verfügung ist durch das Urteil des Verwaltungsgerichts ersetzt worden (Devolutiveffekt) und gilt als inhaltlich mitangefochten (<ref-ruling> E. 1 S. 441 mit Hinweisen).
2. Vorab ist festzuhalten, dass die Beseitigung des Unterstandes und des in den See hinein ragenden Teils des Holzdecks von den Beschwerdeführern nicht mehr bestritten wird. Sie wenden sich einzig dagegen, auch das restliche Holzdeck hinter der Ufermauer auf dem Terrain des Vorgartens zu entfernen und den ursprünglichen Zustand wiederherzustellen.
3. Die Beschwerdeführer berufen sich in erster Linie auf den Grundsatz von Treu und Glauben und machen Vertrauensschutz geltend. Sie vertreten die Ansicht, aufgrund des Hergangs und der abgegebenen Zusicherungen müsse als erstellt gelten, dass der Gemeinderat von Tüscherz-Alfermée das landseitig gelegene Holzdeck genehmigt habe.
3.1 Der in <ref-law> verankerte Grundsatz von Treu und Glauben verleiht einer Person Anspruch auf Schutz des berechtigten Vertrauens in behördliche Zusicherungen oder sonstiges, bestimmte Erwartungen begründendes Verhalten der Behörden. Vorausgesetzt ist weiter, dass die Person, die sich auf Vertrauensschutz beruft, berechtigterweise auf diese Grundlage vertrauen durfte und gestützt darauf nachteilige Dispositionen getroffen hat, die sie nicht mehr rückgängig machen kann; schliesslich scheitert die Berufung auf Treu und Glauben dann, wenn ihr überwiegende öffentliche Interessen gegenüberstehen (<ref-ruling> E. 4.1 S. 170; <ref-ruling> E. 3a S. 36; <ref-ruling> E. 3a S. 387; <ref-ruling> E. 4b S. 254).
3.2 Das Verwaltungsgericht setzt sich im angefochtenen Urteil zunächst ausführlich mit der Bewilligungsfähigkeit des Holzdecks auseinander. Es unterscheidet insbesondere zwischen dem in den See hinaus ragenden und dem an Land erstellten Teil. Zu Letzterem führt es aus, dieser befinde sich in der Uferschutzzone nach Art. 3 Abs. 1 lit. a und Art. 4 Abs. 1 SFG/BE. In dieser Zone dürfen Bauten und Anlagen nur errichtet werden, wenn sie nach ihrem Zweck einen Standort in der Uferschutzzone erfordern, im öffentlichen Interesse liegen und die Uferlandschaft nicht beeinträchtigen (Art. 4 Abs. 1 SFG/BE). Das Verwaltungsgericht hält dazu fest, das Holzdeck diene einzig den Beschwerdeführern als private Anlage und liege daher nicht im öffentlichen Interesse. Darüber hinaus sei es auch nicht standortgebunden, liege doch ein beträchtlicher Teil der Parzelle Nr. 414 gemäss dem Uferschutzplan Nr. 7A "Schlössli" vom 29. November 2001 im Sektor C: Dort sind laut Art. 7.1 der Überbauungsvorschriften (ÜV) Gartenanlagen zonenkonform und kann nach Auffassung des Verwaltungsgerichts auch ein rollstuhlgängiger Zugang zum See geschaffen werden. Auch stehe das Holzdeck in Widerspruch zu Art. 9 ÜV, wonach die natürliche Ufervegetation zu erhalten und zu fördern ist. Folgerichtig gelangt das Verwaltungsgericht zum Schluss, das Deck sei nicht zonenkonform. Dieser Feststellung kann gefolgt werden. Sie wird denn auch von den Beschwerdeführern nicht bestritten.
3.3 Weiter verneint das Verwaltungsgericht auch die Voraussetzungen für eine Ausnahmebewilligung nach Art. 6 Abs. 3 SFG/BE. Diese Bestimmung sieht vor, dass die zuständige Stelle der Justiz-, Gemeinde- und Kirchendirektion aus wichtigen Gründen Ausnahmen von einzelnen Vorschriften gewähren kann, soweit der Zweck des Gesetzes nicht gefährdet wird. Dazu zieht das Verwaltungsgericht in Erwägung, es gelte namentlich zu beachten, dass der Perimeter des massgeblichen Uferschutzplans einzig die Parzelle Nr. 414 umfasse und diese vier verschiedenen Zonen zuweise. Im Rahmen der Planung sei eine spezifisch auf dieses Grundstück zugeschnittene, differenzierte Bauordnung geschaffen worden. So seien Gartenanlagen bzw. Terrassen und Pergolen in den Sektoren C und D ausdrücklich vorgesehen. Angesichts dieser auf das Bauvorhaben der Beschwerdeführer zugeschnittenen Regelung bleibe für eine Ausnahme kein Raum. Auch habe die Anwendung der Vorschriften keine ausgesprochene Unbilligkeit zur Folge, lasse sich doch das streitbetroffene Bauvorhaben nur wenig verschoben auf dem im Sektor C liegenden Teil des Grundstückes zonenkonform verwirklichen. Ebenso sei der Zugang zum See auf anderem Weg ohne Probleme möglich, befinde sich doch östlich der Schutzzone eine Hafenanlage mit einer Treppe und bestehe mit dem Rollstuhlsteg mit Einsteigeplattform im Hafen auch für den heutigen Beschwerdeführer 7 die Möglichkeit, ins Wasser zu gelangen. Die Vorinstanzen hätten zu Recht keine Ausnahmebewilligung nach Art. 6 Abs. 3 SFG/BE gewährt. Auch diese Schlussfolgerung wird von den Beschwerdeführern nicht in Abrede gestellt.
3.4 Indes stützen sich die Beschwerdeführer in ihrer Argumentation auf ein Schreiben des Gemeinderates vom 12. Mai 2004, welches den Titel "Überbauung Schlössli - Stellungnahme zum Umgebungsplan" trägt und hinsichtlich des Holzdecks wie folgt lautet:
"Das geplante Holzdeck auf dem "Schlössli Terrain" wird ebenfalls im Einvernehmen mit den Schutzorganisationen genehmigt, ausgenommen von der Genehmigung ist der in den See hinausragende Teil. Zur Zeit klärt das Statthalteramt mit den zuständigen Instanzen die Bewilligung des in den See hinausragenden Teils ab. Vorbehältlich der Zustimmung des Statthalters stützt die Gemeinde mit den Schutzorganisationen den fraglichen Teil."
Die Beschwerdeführer weisen darauf hin, dass der Gemeinderat bezüglich des in den See hinein ragenden Abschnitts ausdrücklich einen Vorbehalt angebracht und an den Regierungsstatthalter verwiesen habe. Sie, bzw. ihr Architekt, hätten in guten Treuen annehmen dürfen, der Gemeinderat habe das landseitige Holzdeck genau so genehmigt wie die steinerne Bodenpflästerung davor oder die Beseitigung der Thujahecke. Auch wenn von einer "Stellungnahme" die Rede sei, handle es sich bei dem Schreiben doch ganz klar um einen konkreten Genehmigungsbeschluss, der alle Elemente einer Verfügung enthalte, auch wenn diese nicht ausdrücklich als solche gekennzeichnet worden sei. Es sei nicht Aufgabe des Bürgers, die Zuständigkeiten der Behörden zu hinterfragen, solange diese nicht offensichtlich falsch seien.
3.5 Das Verwaltungsgericht hält den Beschwerdeführern zugute, dass sie die Arbeiten erst aufgrund des zitierten Schreibens der Gemeinde vorgenommen haben. Indes sei die Gemeinde klarerweise nicht die allein zuständige Stelle zur Bewilligung von Bauvorhaben in der Uferschutzzone. Der heutige Beschwerdeführer 7 sei bereits im Verfahren um Bewilligung des Sechsfamilienhauses als Vertreter der Bauherrschaft aufgetreten und habe auch im streitigen Verfahren die zur Bewilligung eingereichten Umgebungspläne mit Holzdeck und Unterstand namens der Bauherrschaft unterzeichnet. Für den als Anwalt tätigen Beschwerdeführer 7 müsse erkennbar gewesen sein, dass die Gemeinde das strittige Bauvorhaben nicht allein und ausserhalb eines förmlichen Baubewilligungsverfahrens bewilligen könne und dürfe, zumal sich die fehlende Kompetenz der Gemeinde nach Meinung des Verwaltungsgerichts durch Konsultation des Gesetzestextes ohne weiteres hätte erkennen lassen. Gleiches gelte für den von den Beschwerdeführern beigezogenen Architekten. Dieser habe als Fachperson um die Rechtslage wissen müssen. Schliesslich falle erheblich zu Ungunsten der Beschwerdeführer ins Gewicht, dass diese bereits aus der im Zusammenhang mit der Bewilligung des Sechsfamilienhauses erfolgten Projektänderung betreffend Cheminée-bau und Kaminzug an der Süd-Westfassade gewusst hätten, dass Ausnahmen von den Vorschriften des Uferschutzplans nur vom AGR und nicht von der Gemeinde erteilt werden können. Es müsse somit für alle Beteiligten auf der Hand gelegen haben, dass das Holzdeck aufgrund seiner Dimensionen baubewilligungspflichtig gewesen sei, den Überbauungsvorschriften offenkundig nicht entsprochen habe und von der Gemeinde nicht allein habe bewilligt werden können. Daran ändere nichts, dass die Uferschutzorganisationen ihre Unterstützung bekundet hätten, vermöge doch deren Einverständnis die Zustimmung der staatlichen Behörden nicht zu ersetzen.
Weiter vertritt das Verwaltungsgericht den Standpunkt, die Beschwerdeführer könnten auch aus dem Verhalten des Regierungsstatthalters nichts zu ihren Gunsten ableiten. Selbst wenn dieser am Augenschein vom 8. September 2004 und im folgenden Verfahren tatsächlich nur den in den See hinein ragenden Teil des Holzdecks bemängelt und den Landteil als bewilligt betrachtet hätte, läge nach Meinung des Verwaltungsgerichts kein vertrauensbildender Tatbestand vor. Zu diesem Zeitpunkt sei das Holzdeck längst erstellt gewesen und die Beschwerdeführer hätten aufgrund des Verhaltens des Regierungsstatthalters keinerlei nicht wieder rückgängig zu machende Dispositionen getroffen.
3.6 Diese Würdigung der Umstände durch das Verwaltungsgericht ist verfassungsrechtlich nicht zu beanstanden. Zwar kann das Schreiben der Gemeinde vom 12. Mai 2004 für Unkundige den Anschein erwecken, die Gemeinde verfüge über abschliessende Entscheidbefugnisse. Die Beschwerdeführer haben sich aber insbesondere die Rechtskenntnisse ihres Anwaltes als direkt Mitbetroffenem und Beschwerdeführer 7 sowie die Erfahrung ihres Architekten anrechnen zu lassen (vgl. <ref-ruling> E. 6.2.2 S. 38; <ref-ruling> E. 6a S. 222). In diesem Zusammenhang weist denn das Verwaltungsgericht zu Recht auf das Gesuch der Bauherrschaft vom 27. März 2003 für eine Projektänderung hinsichtlich eines Cheminéeanbaus inklusive Kaminabzug hin: Das Vorhaben hätte einer Ausnahme von den Uferschutzvorschriften bedurft, welche das AGR mit Schreiben vom 16. September 2003 verweigerte. Dies hatte zur Folge, dass das Gesuch abgewiesen und in der Folge Art. 6.5 der Überbauungsvorschriften abgeändert wurde. Spätestens seit diesem Zeitpunkt musste den Beteiligten klar sein, dass die Gemeinde nicht allein über Ausnahmebewilligungen in der Uferschutzzone entscheiden kann. Auch die Änderung der Überbauungsvorschriften musste nach dem kommunalen Beschluss vom 12. Dezember 2003 noch vom AGR genehmigt werden. Zumindest der Beschwerdeführer 7 und der Architekt mussten sich demzufolge aufgrund ihrer Fachkenntnisse in rechtlicher und praktischer Hinsicht der fehlenden Bewilligungskompetenz der Gemeinde für Bauten und Anlagen im Uferschutzbereich bewusst sein. Sie konnten darum aus dem Schreiben "Stellungnahme zum Umgebungsplan" vom 12. Mai 2004 keine weiter gehenden Rechte ableiten.
3.7 Im Zwischenergebnis lässt sich somit festhalten, dass sich die Beschwerdeführer nicht auf den Vertrauensschutz berufen können.
4. Die Beschwerdeführer machen sodann einen Verstoss gegen <ref-law> in Verbindung mit Art. 36 Abs. 2 und 3 BV geltend. Sie empfinden den Wiederherstellungsbefehl zudem als diskriminierend, insbesondere dem Beschwerdeführer 7 als Rollstuhlfahrer gegenüber.
4.1 Gemäss <ref-law> ist das Eigentum gewährleistet. Ein Eingriff in die Eigentumsgarantie bedarf einer hinreichenden gesetzlichen Grundlage. Zudem muss er durch ein öffentliches Interesse gerechtfertigt und verhältnismässig sein (<ref-law>). Ist eine Baute materiell gesetzeswidrig, hat das deshalb noch nicht zur Folge, dass sie abgebrochen werden muss (<ref-ruling> E. 4b S. 255). Auch in einem solchen Falle sind die allgemeinen verfassungs- und verwaltungsrechtlichen Grundsätze zu berücksichtigen. Das Bundesgericht prüft die Voraussetzungen des öffentlichen Interesses und der Verhältnismässigkeit frei. Vor dem Grundsatz der Verhältnismässigkeit hält ein Grundrechtseingriff stand, wenn er zur Erreichung des angestrebten Ziels geeignet und erforderlich ist und das verfolgte Ziel in einem vernünftigen Verhältnis zu den eingesetzten Mitteln, d.h. den zu seiner Verwirklichung notwendigen Freiheitsbeschränkungen, steht (BGE 128 I 1 E. 3e/cc S. 15, mit Hinweisen). So kann die Wiederherstellung des rechtmässigen Zustands unterbleiben, wenn die Abweichung vom Erlaubten nur unbedeutend ist oder die Wiederherstellung nicht im öffentlichen Interesse liegt, ebenso, wenn der Bauherr in gutem Glauben angenommen hat, die von ihm ausgeübte Nutzung stehe mit der Baubewilligung im Einklang, und ihre Fortsetzung nicht schwerwiegenden öffentlichen Interessen widerspricht (<ref-ruling> E. 6 S. 35; <ref-ruling> E. 6 S. 221 mit Hinweisen). Grundsätzlich kann sich auch der Bauherr, der nicht gutgläubig gehandelt hat, gegenüber einem Abbruch- oder Wiederherstellungsbefehl auf den Grundsatz der Verhältnismässigkeit berufen. Er muss indessen in Kauf nehmen, dass die Behörden aus grundsätzlichen Erwägungen, nämlich zum Schutz der Rechtsgleichheit und der baurechtlichen Ordnung, dem Interesse an der Wiederherstellung des gesetzmässigen Zustandes erhöhtes Gewicht beimessen und die dem Bauherrn erwachsenden Nachteile nicht oder nur in verringertem Mass berücksichtigen (<ref-ruling> E. 6.4 S. 39; <ref-ruling> E. 6b S. 224).
4.2 Vorliegend gilt besonderes Augenmerk dem Umstand, dass der Uferschutzplan Nr. 7A speziell auf die Bedürfnisse der Beschwerdeführer zugeschnitten wurde. So besteht denn auf der Parzelle Nr. 414 durchaus die Möglichkeit, im Sektor C des Überbauungsplans ein zonenkonformes Holzdeck zu realisieren (siehe Art. 7.1 der Überbauungsvorschriften). Nötig ist einzig eine Verschiebung. Vor diesem Hintergrund erscheint die Beseitigung der Anlage im Uferschutzbereich als zumutbar. Sie ist zudem das einzige Mittel, um den rechtmässigen Zustand wiederherzustellen. Das Verwaltungsgericht hat die sich gegenüberstehenden privaten Interessen am bequemen Seezugang richtigerweise als weniger gewichtig eingeschätzt als das öffentliche Interesse an der Freihaltung der Uferschutzzone. Wenn die Beschwerdeführer dazu vorbringen, das Holzdeck stehe in Einklang mit der Seegartennutzung, blenden sie den klaren Wortlaut des Gesetzes aus, welches nach Art. 4 Abs. 1 SFG/BE nur Bauten und Anlagen erlaubt, die nach ihrem Zweck einen Standort in der Uferschutzzone erfordern, im öffentlichen Interesse liegen und die Uferlandschaft nicht beeinträchtigen. Dass das Holzdeck diese Anforderungen nicht erfüllt, wurde vor Bundesgericht nicht mehr bestritten (vgl. E. 3.2 hiervor). Hinzu kommt, dass bereits ein Zugang zum und in den See besteht, dies inkl. "Poollift" (Plan 1:100 vom 5. Februar 2004, zuletzt revidiert am 14. September 2004). Selbst wenn der Standort im Hafen nicht optimal erscheinen sollte, ist eine Verschiebung durchaus möglich, ohne dass die Uferschutzzone tangiert wird. Das Argument des Beschwerdeführers 7, wonach er als Rollstuhlfahrer durch den angefochtenen Entscheid diskriminiert werde, greift deshalb nicht.
Nicht ersichtlich ist, weshalb die Beschwerdeführer davon ausgehen, sie hätten anstelle des Holzdecks einen Kiesweg zu erstellen. Der Regierungsstatthalter hat im Entscheid vom 10. Mai 2005 verfügt, der rechtmässige Zustand sei insofern wiederherzustellen, als die bereits vorgenommenen baulichen Massnahmen rückgängig zu machen seien, d.h. bereits errichtete Bauten seien wegen der fehlenden Zonenkonformität zu entfernen. Wie die Gestaltung vorzunehmen sei, wurde nicht genauer definiert. Sie hat sich in jedem Fall an den geltenden Uferschutzvorschriften zu orientieren.
4.3 Demzufolge verletzt der angefochtene Entscheid die bei Grundrechtseingriffen zu beachtende Verhältnismässigkeit nicht. Die diesbezüglichen Rügen sind ebenfalls abzuweisen.
5. Aus den vorstehenden Erwägungen ergibt sich, dass die Beschwerde abzuweisen ist, soweit darauf eingetreten werden kann. Bei diesem Ausgang tragen die Beschwerdeführer die Gerichtskosten (<ref-law>). Parteientschädigungen sind keine zuzusprechen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern unter solidarischer Haftbarkeit auferlegt.
3. Parteientschädigungen werden keine zugesprochen.
4. Dieses Urteil wird den Beschwerdeführern, der Einwohnergemeinde Tüscherz-Alfermée, der Bau-, Verkehrs- und Energiedirektion, dem Verwaltungsgericht des Kantons Bern, Verwaltungsrechtliche Abteilung, und dem Bundesamt für Raumentwicklung schriftlich mitgeteilt.
Lausanne, 15. Mai 2008
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Féraud Scherrer