Sachverhalt:
A. Die Swisscom Broadcast AG stellte am 20. April 2007 bei der Munizipalgemeinde Fieschertal ein Baugesuch für einen Richtfunkspiegel für die Schweizerische Radio- und Fernsehgesellschaft (SRG SSR idée suisse) auf der bestehenden Rundfunk-Basisstation sowie die Installation neuer Antennen für die Versorgung mit digitalem Fernsehen der SRG. Das Vorhaben sah zudem den Ersatz der bestehenden Kabine auf der Parzelle Nr. 745 ausserhalb der Bauzone vor. Das Gesuch wurde mit dem Grundversorgungsauftrag der SRG SSR idée suisse begründet. Der Standort Fieschertal sei für die Versorgung der umliegenden Gemeindegebiete mit "Digital Video Broadcasting Terrestrial" (DVB-T) notwendig. Das Baugesuch wurde im kantonalen Amtsblatt vom 27. April 2007 ausgeschrieben. Dagegen erhoben A._ und verschiedene weitere Personen Einsprache. Die Gemeinde überwies die Akten der kantonalen Baukommission, welche die Baubewilligung am 21. August 2007 erteilte und die Einsprachen abwies, soweit sie darauf eintrat.
A._ und die weiteren Einsprecher beschwerten sich gegen diese Verfügung der kantonalen Baukommission beim Staatsrat des Kantons Wallis. Dabei wurde kein Gesuch um aufschiebende Wirkung gestellt. Die Baugesuchstellerin begann mit den Bauarbeiten. Der Staatsrat wies die Beschwerde am 2. April 2008 ab und entzog einer allfälligen Beschwerde die aufschiebende Wirkung. A._ und weitere Mitbeteiligte zogen diesen Entscheid an das Kantonsgericht Wallis weiter. welches die Verwaltungsgerichtsbeschwerde mit Urteil vom 4. Juli 2008 abwies, soweit es darauf eintrat.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 5. August 2008 beantragen A._ und zahlreiche Mitbeteiligte, das Urteil des Kantonsgerichts sei aufzuheben, die Baubewilligung sei zu widerrufen und der Sendebetrieb auf der Sendeanlage Fieschertal mittels den nachgerüsteten Sendern und Antennen sei unverzüglich einzustellen. Die Anlage sei überdies auf ihren Ursprungszustand zurückzubauen oder eventuell ganz abzubrechen.
C. Die Swisscom Broadcast AG und die kantonale Baukommission beantragen, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Das Kantonsgericht und der Staatsrat schliessen auf Abweisung der Beschwerde. Das Bundesamt für Raumentwicklung (ARE) und das Bundesamt für Umwelt (BAFU) haben sich zur Beschwerde geäussert, ohne einen Antrag zum Ausgang des Verfahrens zu stellen. Die Verfahrensbeteiligten hatten Gelegenheit, sich zu den verschiedenen Eingaben zu äussern und haben davon teilweise Gebrauch gemacht. Sie halten an ihren Anträgen und Rechtsauffassungen fest.

Erwägungen:
1. 1.1 Der angefochtene Entscheid betrifft eine Ausnahmebewilligung im Sinne von Art. 24 RPG (SR 700) für eine Antennenanlage ausserhalb der Bauzone. Er unterliegt der Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>). Die Beschwerdeführer sind Eigentümer bzw. Mieter von Liegenschaften, welche sich innerhalb des praxisgemäss (<ref-ruling>) berechneten Einspracheradius befinden. Sie sind als Adressaten des angefochtenen Entscheids vom umstrittenen Vorhaben besonders berührt und haben ein schutzwürdiges Interesse an der Aufhebung oder Änderung des Urteils des Kantonsgerichts (<ref-law>, <ref-ruling> E. 1.3 S. 252 f.). Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist auf die Beschwerde einzutreten.
2. Die Beschwerdeführer werfen dem Kantonsgericht in erster Linie vor, es habe das Erfordernis der Standortgebundenheit, wie es in Art. 24 lit. a RPG für nicht zonenkonforme Bauten und Anlagen ausserhalb der Bauzonen vorausgesetzt wird, in bundesrechtswidriger Weise bejaht.
2.1 Das Kantonsgericht ist zu Recht davon ausgegangen, das umstrittene Bauvorhaben stelle keine Änderung einer bestehenden Baute im Sinne von Art. 24c RPG dar (vgl. <ref-ruling> E. 3 S. 416). Es hat deshalb Art. 24 RPG seiner Beurteilung zu Grunde gelegt. Nach dieser Bestimmung können nicht zonenkonforme Bauten und Anlagen und deren Zweckänderungen ausserhalb der Bauzonen bewilligt werden, wenn ihr Zweck einen Standort ausserhalb der Bauzonen erfordert und keine überwiegenden Interessen entgegenstehen. Das Kantonsgericht hat das umstrittene Antennenbauprojekt unter Hinweis auf die Rechtsprechung des Bundesgerichts zu den Mobilfunkantennen als standortgebunden im Sinne von Art. 24 lit. a RPG bezeichnet.
2.2 Die Standortgebundenheit im Sinne von Art. 24 lit. a RPG ist nach ständiger bundesgerichtlicher Praxis zu bejahen, wenn eine Anlage aus technischen oder betriebswirtschaftlichen Gründen oder wegen der Bodenbeschaffenheit auf einen Standort ausserhalb der Bauzone angewiesen ist, oder wenn ein Werk aus bestimmten Gründen in einer Bauzone ausgeschlossen ist (vgl. <ref-ruling> E. 3.1 S. 68; <ref-ruling> E. 4a S. 255; <ref-ruling> E. 5a S. 261). Dabei genügt eine relative Standortgebundenheit: Es ist nicht erforderlich, dass überhaupt kein anderer Standort in Betracht fällt; es müssen jedoch besonders wichtige und objektive Gründe vorliegen, die den vorgesehenen Standort gegenüber anderen Standorten innerhalb der Bauzone als viel vorteilhafter erscheinen lassen (Urteil des Bundesgerichts 1A.186/2002 vom 23. Mai 2003 in: ZBl 105/2004 S. 103 E. 3; <ref-ruling> E. 4a S. 362; Walter Haller/Peter Karlen, Raumplanungs-, Bau- und Umweltrecht, 3. Aufl., 1999, S. 195 Rz. 711; Bernhard Waldmann/Peter Hänni, Raumplanungsgesetz, 2006, Art. 24 Rz. 10).
2.3 Antennen für den Mobilfunk (Mobiltelephonie) können nach der Rechtsprechung ausnahmsweise auf einen Standort ausserhalb der Bauzonen angewiesen sein, wenn eine Deckungs- oder Kapazitätslücke aus funktechnischen Gründen mit einem oder mehreren Standorten innerhalb der Bauzonen nicht in genügender Weise beseitigt werden kann bzw. es bei einem Standort innerhalb der Bauzonen zu einer nicht vertretbaren Störung der in anderen Funkzellen des Netzes verwendeten Frequenzen kommen würde. Nicht ausreichend sind dagegen wirtschaftliche Vorteile des gewählten Standorts (z.B. geringere Landerwerbskosten; voraussichtlich geringere Zahl von Einsprachen) oder zivilrechtliche Gründe für die Standortwahl, wie z.B. die Weigerung von Eigentümern, einer Mobilfunkantenne auf ihren Grundstücken innerhalb der Bauzonen zuzustimmen (<ref-ruling> E. 4.3.3 S. 325 f., 409 E. 4.2 S. 417 mit Hinweisen).
Unter besonderen qualifizierten Umständen kann sich allerdings ein Standort ausserhalb der Bauzonen unter Beachtung aller massgebenden Interessen als derart vorteilhaft erweisen, dass er ausnahmsweise in weiteren als den vorne genannten Fällen als standortgebunden im Sinne von Art. 24 lit. a RPG anerkannt werden kann. Im Unterschied zu anderen Bauten und Anlagen (wie Strassen, Parkplätzen, Deponien, Materialgewinnungsanlagen, Sportanlagen usw.) können Mobilfunkantennen ausserhalb der Bauzonen angebracht werden, ohne dafür zwingend neues unüberbautes Nichtbauzonenland in Anspruch zu nehmen. Dies ist der Fall, soweit sie auf bestehende Bauten und Anlagen, wie hier dem bestehenden Antennenmast, montiert werden. Diesem Umstand ist bei der im Rahmen der Standortevaluation vorzunehmenden Interessenabwägung, in welche namentlich Standorte innerhalb aber auch solche ausserhalb der Bauzonen einzubeziehen sind, Rechnung zu tragen. Bei den Standorten ausserhalb der Bauzonen können nicht nur solche ausgewählt werden, die für eine angemessene Abdeckung für die Mobiltelefonie aus technischen Gründen unentbehrlich sind. Vielmehr können sich bei der genannten Abwägung auch Standorte ausserhalb der Bauzonen gegenüber solchen innerhalb der Bauzonen als wesentlich geeigneter erweisen, soweit sie auf bestehenden Bauten und Anlagen angebracht werden können.
Eine entsprechende auf die speziellen Verhältnisse der Mobilfunktechnik zugeschnittene Bejahung der Standortgebundenheit ist jedoch an die folgenden, streng zu beachtenden Bedingungen geknüpft: Grundvoraussetzung einer solchen erweiterten ausnahmsweisen Bejahung der Standortgebundenheit ist, dass die Mobilfunkanlage ausserhalb der Bauzonen keine erhebliche Zweckentfremdung von Nichtbauzonenland bewirkt und nicht störend in Erscheinung tritt. Ein positiver Ausgang der genannten Interessenabwägung reduziert sich somit wie erwähnt grundsätzlich auf Örtlichkeiten, an welchen sich bereits zonenkonforme oder zonenwidrige Bauten und Anlagen befinden. Auch wenn sich ein bereits baulich genutzter Standort im Rahmen der Standortabklärung als klarerweise besser geeignet erweist als ein Standort innerhalb der Bauzonen, so darf eine Ausnahmebewilligung für eine Mobilfunkantenne nur erteilt werden, wenn als zusätzliche Voraussetzung gewährleistet ist, dass dem Vorhaben keine überwiegenden Interessen entgegenstehen (Art. 24 lit. b RPG; <ref-ruling> E. 4.3.3 S. 325 ff.; <ref-ruling> E. 4.2 S. 417 f.).
Diese Rechtsprechung kann grundsätzlich trotz gewisser technischer Unterschiede bei der Netzplanung und der Verwendung der vorhandenen Frequenzen auf die Beurteilung der Standortgebundenheit von Richtfunkantennen und von Sendeanlagen für die Verbreitung von digitalem Fernsehen übertragen werden (vgl. zur analogen Anwendung der Rechtsprechung auf UKW-Sendeanlagen: Urteil des Bundesgerichts 1C_228/2007 vom 28. November 2008 E. 5.4).
2.4 Das Kantonsgericht führt im angefochtenen Urteil aus, am vorgesehenen Baustandort ausserhalb der Bauzone befinde sich bereits eine Rundfunkbasisstation, welche bis November 2007 zur regionalen flächendeckenden Erfüllung des Grundversorgungsauftrags der SRG idée suisse mit analogem Fernsehen gedient habe. Im Zuge des Wechsels vom analogen Fernsehen zum DVB-T sei das analoge Fernsehen abgeschaltet worden und durch DVB-T ersetzt worden, was mit einer Umrüstung der bestehenden Anlagen verbunden gewesen sei. Aus den Planunterlagen ergebe sich, dass dabei am bestehenden Mast lediglich einige neue, kleinere Installationen angefügt worden seien. Das vorbestehende, am Mast befestigte Kabinenhäuschen sei abgerissen und durch ein nur unwesentlich grösseres auf dem Boden angebrachtes Häuschen ersetzt worden. Diese Umrüstung an der bestehenden Basisstation bewirke keine erhebliche Zweckentfremdung von Nichtbauzonenland und trete nicht störender in Erscheinung als dies bisher der Fall gewesen sei. Die Vorteile wögen derart schwer, dass der gewählte Standort ausserhalb der Bauzone im Vergleich zu einem solchen innerhalb der Bauzone als klarerweise besser geeignet erscheine. Die Standortgebundenheit der Anlage sei deshalb zu bejahen.
2.5 Diese Ausführungen, mit welchen die Vorinstanz die Standortgebundenheit des umstrittenen Antennenprojekts bejaht, stehen mit der vorn (E. 2.3) wiedergegebenen Rechtsprechung des Bundesgerichts in verschiedenen Punkten nicht im Einklang. Das Bundesgericht hält die Bejahung der Standortgebundenheit nur für zulässig, wenn sich ein Standort ausserhalb der Bauzonen im Vergleich zu Standorten innerhalb der Bauzonen im Rahmen einer konkreten Interessenabwägung als wesentlich geeigneter erweisen. An einer solchen auf die konkreten Verhältnisse des für das Antennenprojekt in Frage kommenden Einzugsgebiets ausgerichtete Interessenabwägung fehlt es im angefochtenen Urteil. Um überwiegende Interessen in Bezug auf den gutgeheissenen Standort bejahen zu können, muss ein konkreter Vergleich mit möglichen Standorten innerhalb der Bauzonen angestellt werden. Nur wenn sich im Rahmen eines solchen Vergleichs ein Standort ausserhalb der Bauzonen als wesentlich geeigneter erweist als die möglichen Antennenstandorte innerhalb der Bauzonen, kann die Standortgebundenheit bejaht werden. Im vorliegenden Fall ist dabei zu beachten, dass die bisherige Anlage sehr wenig Nichtbauzonenland zweckentfremdet hatte. Das neue Kabinenhäuschen beansprucht mit seiner Grundfläche von 15.5 m2 wesentlich mehr Nichtbauzonenland. Ausserdem sind Gehwegplatten und ein Kabelschacht vorgesehen, die weiteres Nichtbauzonenland versiegeln. All dies ist ebenfalls in die Interessenabwägung der konkreten Standortevaluation einzubeziehen und kann überdies dazu führen, dass dem umstrittenen Vorhaben überwiegende Interessen gemäss Art. 24 lit. b RPG entgegenstehen. Dadurch, dass das Kantonsgericht die Standortevaluation nicht nach den Vorgaben der erwähnten bundesgerichtlichen Rechtsprechung vorgenommen hat, hat es Art. 24 RPG verletzt.
3. Die Beschwerde erweist sich aufgrund der vorstehenden Erwägungen als begründet. Das angefochtene Urteil ist deshalb aufzuheben und die Sache zur Neubeurteilung an das Kantonsgericht zurückzuweisen. Auf die weiteren Rügen der Beschwerdeführer ist unter diesen Umständen nicht weiter einzugehen.
Dem Ausgang des vorliegenden Verfahrens entsprechend sind die Gerichtskosten des bundesgerichtlichen Verfahrens der unterliegenden Beschwerdegegnerin aufzuerlegen (<ref-law>). Den nicht anwaltlich vertretenen Beschwerdeführern wird praxisgemäss keine Parteientschädigung zugesprochen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und das Urteil des Kantonsgerichts des Kantons Wallis vom 4. Juli 2008 aufgehoben. Die Sache wird zur neuen Beurteilung an das Kantonsgericht zurückgewiesen.
2. Die Gerichtskosten von Fr. 3'000.-- werden der privaten Beschwerdegegnerin auferlegt.
3. Es wird keine Parteientschädigung zugesprochen.
4. Dieses Urteil wird den Parteien, der Munizipalgemeinde Fieschertal, der Kantonalen Baukommission und dem Staatsrat des Kantons Wallis, dem Kantonsgericht Wallis, Öffentlichrechtliche Abteilung, sowie dem Bundesamt für Raumentwicklung und dem Bundesamt für Umwelt schriftlich mitgeteilt.
Lausanne, 29. Januar 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Haag