Sachverhalt:
A. Die Swisscom Mobile SA reichte am 2. Dezember 2002 bei der Munizipalgemeinde Zermatt ein Baugesuch für die Errichtung bzw. Änderung der Mobilfunkanlage im Kirchturm der Pfarrkirche ein. Die acht bestehenden GSM-900-Antennen sollen durch vier GSM-900-Antennen und vier kombinierte GSM1800/UMTS-Antennen ersetzt werden. Gegen das Baugesuch erhoben X._, Y._ und weitere Personen Einsprache.
Die Gemeinde Zermatt verlangte von der Swisscom Mobile SA und den übrigen Mobilfunk-Anbietern ein Gesamtkonzept über den zukünftigen Ausbau, die Zusammenarbeit und die koordinierte Planung von Antennenanlagen im Gemeindegebiet. Am 25. September 2003 trat die Gemeinde auf das Baugesuch der Swisscom nicht ein, weil kein Gesamtkonzept vorliege.
B. Gegen den Entscheid der Gemeinde reichte die Swisscom Mobile SA Beschwerde beim Staatsrat des Kantons Wallis ein. Am 5. Oktober 2005 wies der Staatsrat die Beschwerde ab. Er qualifizierte den Nichteintretensentscheid der Gemeinde als Bauabschlagsverfügung. Der Staatsrat hielt es für unzulässig, das Baugesuch wegen Fehlens eines Gesamtkonzepts abzuweisen. Dennoch schützte er den Bauabschlag der Gemeinde: Zum einen bestehe keine Garantie, dass die im Standortdatenblatt zugrundegelegte Strahlungsleistung beim Betrieb der Anlage auch eingehalten werde; zum anderen sei keine zuverlässige Messung der realen Strahlung bei UMTS-Anlagen möglich, weshalb nicht überprüft werden könne, ob die in Betrieb genommene Anlage auch tatsächlich den gesetzlichen Vorgaben genüge.
C. Die Swisscom focht den Staatsratsentscheid mit Verwaltungsgerichtsbeschwerde beim Kantonsgericht an. Dieses hiess die Beschwerde am 19. Mai 2006 gut und wies die Angelegenheit im Sinne der Erwägungen zu neuem Entscheid an die Gemeinde Zermatt zurück.
D. Gegen den kantonsgerichtlichen Entscheid haben X._ und Y._ am 25. Juni 2006 Verwaltungsgerichtsbeschwerde an das Bundesgericht erhoben. Sie beantragen, der angefochtene Entscheid sei aufzuheben und die Baubewilligung sei zu verweigern. Eventuell seien die Akten zur Neubeurteilung und zur Einholung der verschiedentlich beantragten Expertenberichte an das Kantonsgericht zurückzuweisen, soweit nicht das Bundesgericht selbst diese Expertenberichte einholen lasse.
Am 11. August 2006 reichten die Beschwerdeführer eine "Ergänzung" ihrer Beschwerde ein.
E. Die Swisscom Mobile AG beantragt, das Urteil des Kantonsgerichts sei zu bestätigen und die Beschwerde abzuweisen. Auch das Kantonsgericht schliesst auf Abweisung der Beschwerde. Die Einwohnergemeinde Zermatt schliesst auf Gutheissung der Beschwerde und beantragt, ihr sei eine Parteientschädigung zuzusprechen. Der Staatsrat hat auf eine Vernehmlassung verzichtet.
F. Das Bundesamt für Umwelt (BAFU) weist in seiner Vernehmlassung darauf hin, dass der im Standortdatenblatt für OMEN Nr. 2 (Zermatterhof) berechnete Punkt im südlichen Gebäudeteil mit einer NIS-Belastung von 3.49 V/m möglicherweise nicht der am stärksten belastete Punkt sei: Auf der nördlichen Hälfte des Gebäudes sei die Strahlungsbelastung mit 4.6 V/m höher, vorausgesetzt, dass auch dieser Gebäudeteil als Ort mit empfindlicher Nutzung einzustufen sei und keine Gebäudedämpfung geltend gemacht werden könne. Damit werde der Anlagegrenzwert von 5 V/m zu über 80% ausgeschöpft, weshalb eine Abnahmemessung anzuordnen sei.
Die Beschwerdeführer nahmen am 6. November 2006 zu den Vernehmlassungen Stellung und beantragten weitere Abklärungen zur Kontrolle und zur Messung der Mobilfunkstrahlung.
Mit Schreiben vom 31. Oktober 2006 legte die Swisscom Mobile AG dar, weshalb ihres Erachtens die Berechnung des Standortdatenblatts für OMEN Nr. 2 zutreffe. Die Beschwerdeführer nahmen am 15. Dezember 2006 dazu Stellung. Mit Schreiben vom 21. Dezember 2006 reichten die Beschwerdeführer die Publikation des Baugesuchs zum Ausbau des Hotel Zermatterhofs zu den Akten.

Das Bundesgericht zieht in Erwägung:
1. 1.1 Angefochten ist ein kantonal letztinstanzlicher Entscheid, der sich im Wesentlichen auf die Verordnung vom 23. Dezember 1999 über den Schutz vor nichtionisierender Strahlung (NISV; SR 814.710) und damit auf Bundesverwaltungsrecht stützt. Dagegen steht die Verwaltungsgerichtsbeschwerde ans Bundesgericht grundsätzlich offen. Die Beschwerdeführer sind als Bewohner bzw. Eigentümer von Liegenschaften in der Nähe der geplanten Mobilfunkanlage zur Beschwerde legitimiert. Auf die rechtzeitig erhobene Verwaltungsgerichtsbeschwerde ist daher einzutreten.
1.2 Fraglich ist allerdings, ob die Verwaltungsgerichtsbeschwerde zulässig ist, soweit die Beschwerdeführer eine willkürliche Anwendung von Bestimmungen des kantonalen Baurechts, des Bau- und Zonenreglements der Gemeinde sowie des kantonalen Tourismusgesetzes geltend machen.
Regelmässig stellen Bestimmungen zur Zonenkonformität selbständiges kantonales bzw. kommunales Recht dar, das keinen engen Zusammenhang mit Bundesumweltrecht aufweist. Gleiches gilt für Bauvorschriften, beispielsweise zum Schutz des Ortsbildes. Verfassungsverletzungen bei der Auslegung oder Anwendung solcher Bestimmungen können daher grundsätzlich nur mit staatsrechtlicher Beschwerde geltend gemacht werden; zur Beschwerde legitimiert ist nur, wer die Verletzung in rechtlich geschützten eigenen Interessen rügt (Art. 88 OG; vgl. <ref-ruling> E. 2 ff. S. 84 ff. mit Hinweisen).
Allerdings stützen sich die Beschwerdeführer - wie auch die Einwohnergemeinde Zermatt in ihren Vernehmlassungen vor Kantonsgericht und vor Bundesgericht - in erster Linie auf Art. 20 des Walliser Baugesetzes vom 8. Februar 1996 (BauG). Diese Bestimmung betrifft den Schutz vor Immissionen und weist damit einen engen Zusammenhang zum Bundesgesetz über den Umweltschutz vom 7. Oktober 1983 (SR 814.01; USG) und seinen Ausführungsverordnungen, namentlich der NISV, auf. Insofern rechtfertigt es sich, im vorliegenden Fall auch die planungsrechtlichen Rügen im Rahmen der Verwaltungsgerichtsbeschwerde zu behandeln.
1.3 Die am 11. August 2006 bei der Post aufgegebene Beschwerdeergänzung ist verspätet, da die Beschwerdefrist bereits am 26. Juni 2006 abgelaufen war und die Beschwerdeführer keine Frist zur Beschwerdeergänzung beantragt hatten. Die Beschwerdeergänzung ist daher im Folgenden nicht zu berücksichtigen.
2. Streitig ist die Änderung der bestehenden Mobilfunkanlage im Kirchturm der Pfarrkirche Zermatt. Mobilfunkanlagen müssen gemäss <ref-law> die Immissionsgrenzwerte gemäss Anh. 2 NISV an allen Orten einhalten, an denen sich Menschen aufhalten können. Zudem muss die Anlage im massgebenden Betriebszustand an allen Orten mit empfindlicher Nutzung den Anlagegrenzwert (hier: 5 V/m gemäss Ziff. 64 lit. c Anh. 1 NISV) einhalten (<ref-law> i.V.m. Anh. 1 NISV). Diese Vorgaben gelten gleichermassen für alte wie für neue Anlagen (Ziff. 65 Anh. 1 NISV), weshalb offen bleiben kann, ob es sich um die Änderung einer alten oder um eine neue Anlage handelt.
2.1 Nach den Berechnungen im Standortdatenblatt hält die projektierte Anlage sämtliche Vorgaben der NISV ein. Diese Angaben wurden vom BAFU als Fachbehörde des Bundes für den Schutz vor nichtionisierender Strahlung überprüft. Das Bundesamt kommt zum Ergebnis, dass die Strahlungsbelastung am OMEN Nr. 2 (Zermatterhof) höher sei als im Standortdatenblatt berechnet, falls auch der nördliche Gebäudeteil als Ort mit empfindlicher Nutzung zu qualifizieren sei und keine Gebäudedämpfung geltend gemacht werden könne. In diesem Fall betrage die NIS-Belastung 4.6 V/m und nicht bloss 3.49 V/m.
2.2 Die Beschwerdegegnerin macht dagegen geltend, lediglich bei dem im Standortdatenblatt als OMEN 2 ausgewiesenen Punkt gebe es eine Öffnung im Dach in Form einer Lukarne mit Fensteröffnung gegen die Sendeantennen im Kirchturm. An allen anderen Stellen sei das Dach aus Metall und weise keine Öffnungen auf, weshalb eine Gebäudedämpfung von 15 dB eingesetzt werden könne. Aufgrund dieser Dämpfung sei die Strahlungsbelastung an allen anderen Stellen des Gebäudes niedriger als am OMEN 2.
2.3 Die Beschwerdeführer bestreiten diese Darstellung. Sie machen geltend, der oberste Stock des Zermatterhofs weise fast bei jedem Zimmer eine Lukarne auf. Im Übrigen seien Umbauarbeiten beabsichtigt: Die Baute solle erweitert, das Dach angehoben und weitere Fenster eingebaut werden, weshalb mit Grenzwertüberschreitungen zu rechnen sei. Das entsprechende Baugesuch sei am 21. Dezember 2006 publiziert worden.
2.4 Legt man die Berechnung des BAFU zugrunde, d.h. geht man davon aus, dass das Dach des Zermatterhofs auf allen Seiten Öffnungen aufweist und deshalb keine Gebäudedämpfung geltend gemacht werden darf, wäre der Anlagegrenzwert von 5 V/m nicht überschritten, sondern lediglich zu 80% ausgeschöpft, mit der Folge, dass eine Abnahmemessung angeordnet werden müsste. Die Beschwerdegegnerin hat sich mit Schreiben vom 31. Oktober 2006 mit einer solchen Auflage einverstanden erklärt. Die Gemeinde kann daher, sollte sie Zweifel an der Einhaltung des Anlagegrenzwertes im Zermatterhof haben, eine Abnahmemessung anordnen. Dagegen rechtfertigt die vom BAFU berechnete Strahlungsbelastung nicht den Bauabschlag. Insofern kann offen bleiben, ob die Darstellung der Beschwerdegegnerin oder diejenige der Beschwerdeführer zum bestehenden Dach des Zermatterhofs und seinen Öffnungen zutrifft.
2.5 Zum Zeitpunkt des verwaltungsgerichtlichen Entscheids lag unstreitig noch kein Baugesuch für den Ausbau des Zermatterhofs vor. Ist das Bundesgericht, wie im vorliegenden Fall, an den festgestellten Sachverhalt gemäss Art. 105 Abs. 2 OG gebunden, können nachträgliche Veränderungen des Sachverhalts in der Regel nicht mehr berücksichtigt werden (vgl. <ref-ruling> E. 1c S. 99 f. mit Hinweis). Insofern ist die Frage, wie sich ein solches Baugesuch auf die Bewilligungsfähigkeit der streitigen Antennenanlage auswirken würde, im vorliegenden Verfahren nicht zu beurteilen. Immerhin rechtfertigen sich einige Hinweise zum weiteren Vorgehen, sollte tatsächlich ein solches Baugesuch gestellt werden:
Wie das Bundesgericht mehrfach entschieden hat (vgl. <ref-ruling> E. 3 und 4 S. 245 ff.; Entscheid 1A.194/2001 vom 10. September 2002 E. 2, publ. in: URP 2002 S. 780), darf die Bewilligung einer Mobilfunkanlage nicht dazu führen, dass zonenkonforme Nutzungsmöglichkeiten auf den Nachbargrundstücken nicht mehr ausgenützt werden können. Vielmehr muss sichergestellt werden, dass die Antennenanlage jeweils angepasst wird, um die Anlagegrenzwerte auch nach der Realisierung von Nutzungsreserven an den neu entstehenden Orten mit empfindlichen Nutzungen einzuhalten. Die Publikation eines (bewilligungsfähigen) Baugesuchs für den Ausbau des Zermatterhofs wäre somit eine Veränderung des massgeblichen Sachverhalts, die von der Gemeinde berücksichtigt werden müsste. Die Beschwerdegegnerin müsste dann nachweisen, dass der Anlagegrenzwert der NISV auch in den neu entstehenden Orten mit empfindlicher Nutzung eingehalten wird; gegebenenfalls müsste hierfür die Strahlungsleistung der Antennen reduziert werden.
3. Der Staatsrat verweigerte die Baubewilligung, weil nicht gewährleistet sei, dass nicht mit einer höheren als der angegebenen Leistung und mit anderen Winkelbereichen gesendet werde, als im Standortdatenblatt angegeben wurde.
Das Kantonsgericht hielt die Bedenken des Staatsrats zwar für berechtigt, qualifizierte die Bewilligungsverweigerung aber als unverhältnismässig. Es verwies auf die am 31. Dezember 2006 vorgesehene Inbetriebnahme des sogenannten Qualitätssicherungssystems (QS-System), mit dem die Einhaltung der bewilligten Parameter im Sendebetrieb überprüft werden könne. Damit werde dem schutzwürdigen Interesse der Anwohner, die Einhaltung der NIS-Grenzwerte durch objektive und überprüfbare Vorkehren sicherzustellen, genügend Rechnung getragen.
3.1 Die Beschwerdeführer machen geltend, das vom BAFU empfohlene Kontrollsystem entspreche nicht den Anforderungen der bundesgerichtlichen Rechtsprechung, die objektive bauliche Vorkehrungen verlange (<ref-ruling> E. 4 S. 379 ff. und Entscheid 1A.160/2004 vom 10. März 2005 E. 3.3, publ. in: URP 2005 S. 576). Sie halten das vorgesehene Kontrollsystem und die darin vorgesehenen Fristen für die Übermittlung und Aufbewahrung von Fehlermeldungen und die Behebung festgestellter Überschreitungen für ungenügend. Das System sei angesichts der grossen Anzahl von Antennenstandorten und Datenpunkten auch nicht realisierbar: Die Beschwerdeführer schätzen, dass mindestens 130 Personen ständig beschäftigt werden müssten, um die Datenmenge nur annähernd seriös zu überprüfen. Sie bezweifeln auch, dass der Kanton Wallis in der Lage sei, die gebotene Kontrollfunktion wahrzunehmen. Weiter machen sie geltend, das QS-System könne erst auf Mitte 2007 eingeführt werden, weil erst dann die Resultate der Kabeldämpfungsmessungen verfügbar sein würden, die für das Funktionieren des Systems erforderlich seien. Die Beschwerdeführer stellen in diesem Zusammenhang diverse Anträge:
- Die Beschwerdegegnerin und das BAFU hätten nachzuweisen, dass das QS-System per 1. Januar 2007 definitiv eingeführt werde und die Netzbetreiber über die notwendigen Installationen verfügten;
- Das BAFU habe das vorgesehene Kontrollsystem offenzulegen;
- Der Kanton Wallis sei anzufragen, ob er über die notwendigen Kontrollinstrumente und Ausbildung des Personals verfüge, um die späteren Stichproben auf Einhaltung der bewilligten Werte und der Einhaltung der Grenzwerte durchzuführen;
- Das BAFU sei zu einer Stellungnahme einzuladen, ob die Anpassung der Dämpfungsglieder an die variablen Anforderungen der Sendeleistung (als Alternative zum QS-System) auch anders als durch eine mechanische Vorkehrung vorgenommen werden könnte.
3.2 Die Beschwerdegegnerin bestätigt in ihrer Vernehmlassung, dass das im Rundschreiben des BAFU vom 16. Januar 2006 beschriebene Kontrollsystem rechtzeitig implementiert werde. Die hierfür erforderliche Software zur Überwachung der Sendeleistung sei bei der Swisscom Mobile bereits in Betrieb; diese informiere die kantonalen NIS-Fachstellen, das BAFU und das BAKOM alle drei Monate über den Stand der Umsetzung der Datenbanklösung. Ende 2006 werde eine erste Kontrolle zum ordnungsgemässen Funktionieren des Systems durchgeführt; anschliessend würden die Erfahrungen mit den implementierten QS-Systemen ausgewertet und diese bei Bedarf angepasst.
3.3 Das Bundesgericht hat mehrfach entschieden, dass das vom BAFU empfohlene Qualitätssicherungssystem eine zulässige Alternative zur Kontrolle durch bauliche Vorkehrungen darstellt und grundsätzlich den Anforderungen der bundesgerichtlichen Rechtsprechung an eine wirksame Kontrolle der Emissionsbegrenzungen genügt (vgl. Entscheid 1A.57/2006 vom 6. September 2006 E. 5.1 u. 5.2; vgl. auch Entscheide 1A.54/2006 vom 10. Oktober 2006 E. 5; 1A.60/2006 vom 2. Oktober 2006 E. 3). Auf diese Entscheide wird verwiesen.
Wie das BAFU zutreffend ausführt, soll mit den vorgeschriebenen Audits durch unabhängige, externe Prüfstellen nicht jeder einzelne Datenpunkt überprüft werden. Vielmehr soll das korrekte Funktionieren des gesamten QS-Systems, bestehend aus den Datenbanken, der Software, den Prozessen, der Zuständigkeit und dem Reporting, überprüft werden. Ist einmal der korrekte Ablauf der Systemfunktionen nachgewiesen, erübrigt sich die Kontrolle jedes einzelnen Datenelementes. Die Auditfirmen und bei Bedarf die Vollzugsbehörde können sich daher auf Stichprobenkontrollen beschränken. Insofern erscheinen die Befürchtungen der Beschwerdeführer, wonach das vorgesehene Kontrollsystem von vornherein nicht realisierbar sei und die Kapazitäten von Auditfirmen und kantonalen Vollzugsbehörden überschreite, unbegründet.
Das Kantonsgericht hat im angefochtenen Entscheid festgehalten, dass die Gemeinde die Verpflichtung zur Einbindung der Mobilfunkanlage in das QS-System der Swisscom in die Baubewilligung aufnehmen müsse (E. 6.1 S. 18 des angefochtenen Entscheids). Vor Erteilung der Baubewilligung müsse sie eine Beurteilung der kantonalen Vollzugsbehörde, d.h. der kantonalen Umweltschutzfachstelle einholen, um sich zu vergewissern, dass die Auflagen gemäss Rundschreiben des BAFU erfüllt seien; allfällige Auflagen der kantonalen Fachstelle seien in die Baubewilligung zu integrieren (E. 6.2.2 S. 19 oben). Damit ist sichergestellt, dass die Antennenanlage nur in Betrieb genommen werden kann, wenn das Qualitätssicherungssystem der Beschwerdegegnerin funktioniert und die Einhaltung der bewilligten Parameter effektiv kontrolliert.
4. Der Staatsrat begründet den Bauabschlag zusätzlich mit dem Fehlen eines zuverlässigen Messsystems für UMTS-Strahlung.
Dagegen ging das Kantonsgericht, gestützt auf die bundesgerichtliche Rechtsprechung (vgl. insbesondere Entscheid 1A.148/2002 vom 12. August 2003) davon aus, dass es unverhältnismässig sei, die Inbetriebnahme von UMTS-Anlagen vom Vorliegen einer ausgefeilten Messtechnik abhängig zu machen, sondern es genüge, Abnahmemessungen vorerst gestützt auf den Entwurf zur Messempfehlung des BUWAL und des Bundesamtes für Metrologie und Akkreditierung (METAS) vom 17. September 2003 vorzunehmen. Sobald die Fachstellen des Bundes definitive Messvorschriften verordnet haben werden, seien dann verlässliche Kontrollmessungen durchzuführen.
4.1 Das Bundesgericht hat sich in einem neuen Urteil (1A.57/2006 vom 6. September 2006 E. 6) nochmals mit der Frage der Messbarkeit von UMTS-Strahlung beschäftigt. Gestützt auf den Fachbericht des BAFU nahm es an, dass heute Messsysteme existieren, die UMTS-Strahlung zuverlässig messen können und dass das von BAFU und METAS empfohlene Messverfahren für den Nachweis der Einhaltung der Überschreitung der Anlagegrenzwerte geeignet sei. Die Streuung der Messwerte habe sich beträchtlich verringert, nachdem sämtliche Messlabors, die für Code-selektive UMTS-Messungen akkreditiert sind, ihre Messgeräte beim METAS hätten nachkalibrieren lassen; die Messunsicherheit liege heute im gleichen Bereich wie bei Messungen von GSM-Strahlung.
4.2 Die Beschwerdeführer bezweifeln diese Aussage und verlangen präzise Angaben zur Höhe der Messunsicherheit. Zudem sind sie der Auffassung, dass die UMTS-Messempfehlungen vom Bundesrat in Form einer Verordnung erlassen werden müssten.
4.3 Gemäss Art. 12 Abs. 2 Satz 2 und Art. 14 Abs. 2 Satz 2 NISV empfiehlt das BAFU geeignete Mess- und Berechnungsmethoden, um die Einhaltung der Anlage- und Immissionsgrenzwerte zu kontrollieren. Die Messempfehlungen sind Vollzugshilfen des BAFU an die kantonalen Vollzugsbehörden, um eine einheitliche Vollzugspraxis zu ermöglichen. Die kantonalen Behörden sind jedoch, wie der Name ("Empfehlung") bereits ausdrückt, nicht strikt an die Vorgaben des BAFU gebunden, sondern können im Einzelfall eine andere Lösung wählen, wenn diese ebenso tauglich und bundesrechtskonform ist. Im Übrigen geben die Messempfehlungen des BAFU und des METAS als Fachbehörden des Bundes Auskunft über den Stand von Wissenschaft und Technik und entsprechen insoweit Sachverständigengutachten. Es handelt sich somit nicht um Rechtsnormen, die auf dem Verordnungsweg erlassen werden müssten.
4.4 Seit drei Jahren liegt eine Empfehlung des BUWAL und des METAS für die Messung von UMTS-Strahlung in Form eines Entwurfs vor. Dieser Entwurf wurde seither in der Praxis erprobt, nachdem Messlabors mit den UMTS-spezifischen Messgeräten ausgerüstet und für UMTS-Messungen akkreditiert worden sind. Inzwischen ist diese Erprobungsphase abgeschlossen: Das BAFU teilt in seiner Vernehmlassung mit, dass es die Messempfehlung voraussichtlich Ende 2006 finalisieren werde. Damit wird 2007 eine definitive Messempfehlung vorliegen, auf deren Grundlage seriöse Messungen durchgeführt werden können.
Unter diesen Umständen kann die Bewilligung für UMTS-Mobilfunkanlagen nicht aufgrund der fehlenden Messbarkeit der UMTS-Strahlung verweigert werden. Weitere Abklärungen zu dieser Frage erscheinen im gegenwärtigen Zeitpunkt nicht geboten.
5. Das Kantonsgericht ging davon aus, dass die Mobilfunkanlage in der Zone für öffentliche Bauten und Anlagen zonenkonform sei (E. 3 des angefochtenen Entscheids). Eine gesetzliche Pflicht zu einer Gesamtplanung und Koordination für Bauvorhaben dieser Art bestehe weder auf der Ebene des Bundes, noch des Kantons, noch der Gemeinde. Dann aber dürfe der Bauabschlag nicht wegen Fehlens eines Gesamtkonzepts aller Mobilfunkanbieter erteilt werden (E. 4 des angefochtenen Entscheids).
Diese Auffassung hatte bereits der Staatsrat vertreten: Die Baubewilligung sei eine Polizeierlaubnis, auf deren Erteilung Anspruch bestehe, sofern die gesetzlichen Voraussetzungen erfüllt seien (Art. 24 Abs. 1 der kantonalen Bauverordnung vom 2. Oktober 1996). Vorliegend seien keine materiellen Vorschriften oder planerischen Vorgaben des kantonalen oder kommunalen Rechts ersichtlich, welche es ermöglichen würden, den Standort im Rahmen einer umfassenden Interessenabwägung zu prüfen bzw. die Bewilligung von der Beibringung eines Gesamtkonzepts aller gegenwärtigen und zukünftigen Antennenstandorte aller Mobilfunkbetreiberinnen abhängig zu machen (E. 2.4 S. 7 des Staatsratsentscheids).
5.1 Die Beschwerdeführer machen dagegen geltend, Art. 20 Abs. 2 BauG ermögliche es der Gemeinde, Auflagen und Bedingungen zum Schutz der Umwelt in die Bewilligung aufzunehmen oder Projektänderungen zu verlangen, insbesondere um schädliche Immissionen für die Nachbarschaft einzudämmen. Dies genüge als gesetzliche Grundlage für die Anordnung einer Koordinationspflicht und für die Einreichung eines Gesamtkonzepts. Zusätzlich führen sie das Tourismusgesetz vom 9. Februar 1996 an, das die Gemeinden zur Förderung eines qualitativ hochstehenden Tourismus und zur Achtung der natürlichen und kulturellen Gegebenheiten verpflichte. Schliesslich seien nach Art. 18 des Bau- und Zonenreglements der Gemeinde in der streitbezogenen Zone nur Einrichtungen zulässig, die im öffentlichen Interesse liegen. Es sei Aufgabe der Gemeinde, das öffentliche Interesse zu bestimmen und Auflagen und Projektänderungen zum Schutz der Nachbarschaft zu verlangen.
5.2 Der Immissionsschutz ist bundesrechtlich im USG und den darauf gestützten Verordnungen geregelt. Für den Schutz vor nichtionisierender Strahlung, die beim Betrieb ortsfester Anlagen erzeugt wird, hat der Bundesrat die NISV erlassen; diese Verordnung regelt insbesondere auch die Immissionen von Mobilfunksendeanlagen (vgl. Ziff. 6 Anh. 1 NISV). Diese Regelung ist abschliessend, und zwar nicht nur hinsichtlich des Schutzes vor schädlicher und lästiger Strahlung, sondern auch im Bereich des vorsorglichen Immissionsschutzes (vgl. <ref-ruling> E. 3c S. 403). Für das kommunale und kantonale Recht bleibt deshalb kein Raum (so auch Benjamin Wittwer, Bewilligung von Mobilfunkanlagen, Dissertation Zürich 2006, S. 10 und S. 91 f.; Arnold Marti, Urteilsanmerkung, ZBl 107/2006 S. 213). Insofern findet die kantonale Regelung zum Immissionsschutz in Art. 20 BauG keine Anwendung. Die Gemeinde kann gestützt auf diese Bestimmung keine Auflagen oder Bedingungen verfügen, die über die Anforderungen der NISV hinausgehen.
5.3 Dies bedeutet nicht, dass die Gemeinde keinerlei Möglichkeiten hätte, auf die Standorte von Mobilfunkanlagen Einfluss zu nehmen: Im Rahmen ihrer bau- und planungsrechtlichen Zuständigkeiten ist sie grundsätzlich befugt, Bau- und Zonenvorschriften in Bezug auf Mobilfunksendeanlagen zu erlassen, sofern sie die bundesrechtlichen Schranken, die sich insbesondere aus dem Bundesumwelt- und -fernmelderecht ergeben, beachtet (so schon Urteil 1A.280/2004 vom 27. Oktober 2005, E. 3.7.3, publ. in: ZBl 107/2006 S. 207). Ausgeschlossen sind nach dem oben (E. 5.2) Gesagten bau- oder planungsrechtliche Vorschriften zum Schutz der Bevölkerung vor nichtionisierender Strahlung. Überdies dürfen die kommunalen Vorschriften nicht die in der Fernmeldegesetzgebung konkretisierten öffentlichen Interessen verletzen, d.h. sie müssen den Interessen an einer qualitativ guten Mobilfunkversorgung und an einem funktionierenden Wettbewerb zwischen den Mobilfunkanbietern Rechnung tragen (vgl. Art. 1 des Fernmeldegesetzes vom 30. April 1997 [FMG; SR 784.10]).
Werden die Zielsetzungen der Fernmeldegesetzgebung eingehalten, so sind ortsplanerische Bestimmungen, die anderen als umweltschutzrechtlichen Interessen dienen, wie z.B. der Wahrung des Charakters oder der Wohnqualität eines Quartiers, grundsätzlich möglich (vgl. dazu Wittwer, a.a.O., S. 97 f.; Marti, a.a.O., S. 213). In der Regel wird es sich dabei um Negativplanungen handeln, d.h. um Zonenvorschriften, die Mobilfunkanlagen in bestimmten Zonen grundsätzlich ausschliessen. Denkbar sind aber auch positive Planungen, die besondere Zonen für Mobilfunksendeanlagen ausweisen, sofern es sich um Standorte handelt, die sich besonders gut eignen und eine genügende Versorgung durch alle Mobilfunkanbieter ermöglichen. Der Konzentration von Sendestandorten innerhalb des Siedlungsgebiets werden allerdings durch die Anlagegrenzwerte der NISV enge Grenzen gesetzt (vgl. Ziff. 62 Abs. 1 Anh. 1 NISV, wonach alle Mobilfunksendeantennen, die in einem engen räumlichen Zusammenhang stehen, als eine Anlage gelten und gemeinsam den Anlagegrenzwert einhalten müssen).
5.4 Voraussetzung ist aber in jedem Fall eine gesetzliche Grundlage im kommunalen oder kantonalen Recht (so auch Wittwer, a.a.O., S. 96 f.; Marti, a.a.O., S. 213). Im vorliegenden Fall haben der Staatsrat und das Kantonsgericht willkürfrei das Vorliegen einer solchen Rechtsgrundlage verneint. Besteht somit keine entsprechende Grundlage in den Bau- oder Zonenvorschriften, kann die Gemeinde weder Einfluss auf die Standortwahl nehmen noch, wie im vorliegenden Fall, ein Gesamtkonzept aller Mobilfunkbetreiberinnen für die Standortplanung innerhalb der Bauzone verlangen.
6. Die Beschwerdeführer bringen schliesslich vor, die geltenden Grenzwerte der NISV seien zu hoch und verstiessen gegen das Vorsorgeprinzip gemäss <ref-law> sowie gegen das Grundrecht auf körperliche Unversehrtheit. Diese Frage hat das Bundesgericht schon mehrfach geprüft (grundlegend <ref-ruling> E. 4 S. 404 ff.; vgl. aus jüngerer Zeit die Entscheide 1A.218/2004 vom 29. November 2005 E. 3; 1A.280/2004 vom 27. Oktober 2005 E. 2; 1A.202/2004 vom 3. Juni 2005 E. 2; 1A.146/2004 vom 15. Februar 2005 E. 3; 1A.208/2004 vom 19. Januar 2005 E. 2 und 1A.60/2006 vom 2. Oktober 2006 E. 2). Auf diese Entscheide kann verwiesen werden.
7. Schliesslich rügen die Beschwerdeführer den Kostenentscheid des Kantonsgerichts als willkürlich. Das Kantonsgericht habe nur ihnen und nicht der Gemeinde Kosten auferlegt, mit der Begründung, die Gemeinde verfolge keine Vermögensinteressen. Die Beschwerdeführer verfolgten aber ebenfalls keine Vermögensinteressen, sondern träten als Anwälte für Natur und Mensch auf. Angesicht der neu aufgeworfenen Fragen, über die höchstrichterlich noch nicht entschieden worden sei, rechtfertige es sich, vom Regelfall abzuweichen und auch ihnen keine Kosten aufzuerlegen.
7.1 Willkür liegt nach der Rechtsprechung nicht schon dann vor, wenn eine andere Lösung ebenfalls vertretbar erscheint oder sogar vorzuziehen wäre. Das Bundesgericht weicht vom Entscheid der kantonalen Instanz nur ab, wenn dieser offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 2a S. 168; <ref-ruling> E. 3a S. 15, 129 E. 5b S. 134; je mit Hinweisen).
7.2 Im vorliegenden Fall hat das Kantonsgericht die Kosten nach dem Unterliegerprinzip verteilt, das in Art. 89 Abs. 1 des Gesetzes über das Verwaltungsverfahren und die Verwaltungsrechtspflege vom 6. Oktober 1976 (VVRG) als Regel vorgesehen ist. Der Gemeinde wurden, Art. 89 Abs. 4 VVRG entsprechend, keine Kosten auferlegt, weil diese als Vorinstanz, in ihrem amtlichen Wirkungskreis als Baubewilligungsbehörde, am Verfahren beteiligt war. Die Frage, ob ein Beteiligter Vermögensinteressen oder ideelle Interessen vertritt, spielt nach der gesetzlichen Konzeption nur für die Frage eine Rolle, ob einer beteiligten Behörde ausnahmsweise Kosten aufzuerlegen sind. Im Übrigen haben die Beschwerdeführer, die sich am kantonsgerichtlichen Verfahren mit eigenen Anträgen beteiligten, auch eigene Interessen vertreten, indem sie versuchten, die Mobilfunkstrahlung von ihrem Wohnort fernzuhalten.
Insofern kann dem Kantonsgericht, das sich an den im Gesetz vorgesehenen Regelfällen orientierte, keine Willkür vorgeworfen werden.
8. Nach dem Gesagten ist die Verwaltungsgerichtsbeschwerde abzuweisen. Bei diesem Ausgang des Verfahrens werden die Beschwerdeführer kosten- und entschädigungspflichtig (Art. 156 und 159 OG) und haben - wie auch die Gemeinde Zermatt - keinen Anspruch auf eine Parteientschädigung.

Demnach erkennt das Bundesgericht:
1. Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2. Die Gerichtsgebühr von Fr. 4'000.-- wird den Beschwerdeführern auferlegt.
3. Die Beschwerdeführer haben die Swisscom Mobile AG für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, der Munizipalgemeinde Zermatt, dem Staatsrat des Kantons Wallis und dem Kantonsgericht Wallis, Öffentlichrechtliche Abteilung, sowie dem Bundesamt für Umwelt schriftlich mitgeteilt.
Lausanne, 10. Januar 2007
Im Namen der I. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin: