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.