Sachverhalt:
A. Die Foot Locker Retail Inc. (Gesuchstellerin und Beschwerdegegnerin) beantragte am 6. April 2004 Markenschutz für das Zeichen COLORADO (fig.) für folgende Waren (Markeneintragungsgesuch 52266/2004) der Klassen
18: "Taschen, nämlich Schultertaschen, Allzwecksporttaschen, Tornister, Rucksäcke, Handtaschen, Kleidersäcke, Trag- und Reisetaschen"; sowie
25: "Kopfbedeckungen, Schuhwaren, Schuhe und Freizeitbekleidung, nämlich Freizeithosen, Hemden, Unterhosen, Jacken, Jeans, Westen, Sweatshirts, Jogginganzüge, T-Shirts, Trainerhosen, kurze Hosen, Pullover und Socken."
Die schwarz-weiss hinterlegte Wort-/Bildmarke sieht wie folgt aus:
Bild nicht abrufbar
Das Institut für geistiges Eigentum (IGE) wies das Markeneintragungsgesuch mit Verfügung vom 23. Februar 2005 gestützt auf Art. 2 lit. c in Verbindung mit Art. 30 Abs. 2 lit. c MSchG (SR 232.11) zurück. Zur Begründung führte das IGE im Wesentlichen aus, in schweizerischen Verkehrskreisen werde COLORADO mit den USA in Verbindung gebracht und sowohl Kleidungsstücke wie Lederwaren würden in diesem US-Bundesstaat auch hergestellt, weshalb das Zeichen für Waren, die nicht aus den USA stammen, täuschend sei.
B. Mit Entscheid vom 5. Mai 2006 hiess die Eidgenössische Rekurskommission für Geistiges Eigentum die Beschwerde der Gesuchstellerin gut, hob die Verfügung des IGE vom 23. Februar 2005 auf und wies dieses an, dem Markeneintragungsgesuch 52266/2004 vollumfänglich zu entsprechen. Sie ging zwar mit dem IGE davon aus, dass der Wortbestandteil COLORADO als geografischer Hinweis - auf den Bundesstaat Colorado im mittleren Westen der USA - verstanden werde. Sie legte dar, Warenmarken mit geografischen Angaben würden in der Praxis nur mit einem Zusatz in der Warenliste eingetragen, wonach die beanspruchten Waren aus dem Land stammen müssen, auf das die Herkunftsangabe hinweist. Diese Praxis sei in der Lehre bisher nicht beanstandet worden. Die Rekurskommission kam aber zum Schluss, die Praxis müsse geändert werden, denn es bestehe kein überwiegendes öffentliches Interesse an der präventiven Nichteintragung von Marken, von denen ein täuschender Gebrauch gemacht werden könnte. Sie werde daher in Zukunft Marken mit einem geografischen Inhalt ohne entsprechende Einschränkung der Waren- und Dienstleistungsliste zulassen, soweit kein qualifiziertes Schutzbedürfnis vorliege.
C. Mit Verwaltungsgerichtsbeschwerde vom 2. Juni 2006 beantragt das Eidgenössische Justiz- und Polizeidepartement, der Entscheid der Eidgenössischen Rekurskommission für Geistiges Eigentum vom 5. Mai 2006 sei aufzuheben und das Markeneintragungsgesuch 52266/2004 für Waren der Klassen 18 und 25 sei nur mit folgender Einschränkung zuzulassen: "Alle vorgenannten Waren US-amerikanischer Herkunft".
D. Die Gesuchstellerin und die Eidgenössische Rekurskommission für geistiges Eigentum beantragen in ihren Vernehmlassungen, die Beschwerde sei abzuweisen.

Das Bundesgericht zieht in Erwägung:
1. Das Bundesgericht beurteilt gemäss Art. 97 OG letztinstanzlich Verwaltungsgerichtsbeschwerden gegen Verfügungen im Sinne von Artikel 5 des Verwaltungsverfahrensgesetzes vom 20. Dezember 1968 (Abs. 1), die unter anderem gegen Entscheide eidgenössischer Rekurskommissionen zulässig sind (Art. 98 lit. e OG). Ein Ausschlussgrund im Sinne der Art. 99 ff. OG liegt nicht vor. Die Beschwerde ist fristgerecht (Art. 106 in Verbindung mit 34 Abs. 1 lit. c OG) vom zuständigen Departement (<ref-ruling> E. 2) eingereicht worden.
1.1 Das Bundesgericht darf - von einer hier nicht vorliegenden Ausnahme abgesehen - weder zugunsten noch zuungunsten der Parteien über deren Begehren hinausgehen (Art. 114 Abs. 1 OG). Es kann daher dem beschwerdeführenden Departement nicht mehr zusprechen, als es verlangt. Es kann somit die Eintragung der Wort-/Bildmarke COLORADO nicht verweigern, sondern hat im Falle der Gutheissung der Beschwerde die Eintragung der Marke entsprechend dem Rechtsbegehren des Beschwerdeführers mit der Einschränkung auf US-amerikanische Waren anzuordnen (vgl. <ref-ruling> E. 9 S. 300; <ref-ruling> E. 1b S. 352 f.).
1.2 Im verwaltungsgerichtlichen Beschwerdeverfahren sind grundsätzlich nur Rechtsverhältnisse zu überprüfen, zu denen die zuständige Verwaltungsbehörde vorgängig verbindlich - in Form einer Verfügung - Stellung genommen hat; die Verfügung definiert den Anfechtungsgegenstand (<ref-ruling> E. 2a S. 36 mit Verweisen). Das IGE hat hier die Eintragung der Wort-/Bildmarke COLORADO in der Verfügung vom 23. Februar 2005 überhaupt verweigert. Entgegen den von der Rekurskommission in ihrer Vernehmlassung geäusserten Bedenken halten sich jedoch die im vorliegenden Verfahren zu beurteilenden Rechtsbegehren im Rahmen des durch diese Verfügung umschriebenen Anfechtungsgegenstands. Denn mit der - auf Waren bestimmter Herkunft - eingeschränkten Eintragung der beanspruchten Marke begehrt das beschwerdeführende Departement nicht etwas anderes, sondern weniger als die vollständige Verweigerung der Eintragung.
1.3 Die Feststellung des Sachverhalts bindet das Bundesgericht, wenn wie hier eine richterliche Behörde als Vorinstanz entschieden und den Sachverhalt nicht offensichtlich unrichtig, unvollständig oder unter Verletzung wesentlicher Verfahrensbestimmungen festgestellt hat (Art. 105 Abs. 2 OG). Neue tatsächliche Behauptungen und Beweismittel sind grundsätzlich nur soweit zulässig, als sie die Vorinstanz von Amtes wegen hätte erheben müssen und deren Nichterheben eine Verletzung wesentlicher Verfahrensvorschriften darstellt (<ref-ruling> E. 1 S. 456 f.). Dagegen prüft das Bundesgericht auf Verwaltungsgerichtsbeschwerde frei, ob die Vorinstanz Bundesrecht verletzt oder ihr Ermessen überschritten oder missbraucht hat (Art. 104 lit. a OG).
2. Nach Art. 2 lit. c MSchG sind irreführende Zeichen vom Markenschutz absolut ausgeschlossen. Dieser Ausschlussgrund gilt als Schutzverweigerungsgrund auch gemäss Art. 6quinquies lit. B Ziffer 3 PVÜ (Pariser Verbandsübereinkunft zum Schutz des gewerblichen Eigentums, revidiert in Stockholm am 14. Juli 1967; SR 0.232.04).
2.1 Irreführend ist eine Marke unter anderem dann, wenn sie eine geografische Angabe enthält oder gar ausschliesslich aus einer geografischen Bezeichnung besteht, und damit die Adressaten zur Annahme verleitet, die Ware stamme aus dem Land oder dem Ort, auf den die Angabe hinweist, obschon das in Wirklichkeit nicht zutrifft. Keine Gefahr der Irreführung besteht dagegen, wenn die geografische Angabe erkennbar Fantasiecharakter hat, offensichtlich nicht als Produktions-, Fabrikations- oder Handelsort in Frage kommt, als Typenbezeichnung erkannt wird oder sich im Verkehr als Kennzeichen für ein bestimmtes Unternehmen durchgesetzt hat (<ref-ruling> E. 2.2; <ref-ruling> E. 1a S. 328; Urteil des Bundesgerichts 4A.5/1994 vom 2. August 1994, E. 3a, publ. in: PMMBl 1994 I S. 76 ff.).
Ob eine geografische Bezeichnung, die als Bestandteil einer Marke verwendet werden soll, zur Täuschung des Publikums geeignet ist, entscheidet sich nicht allgemein, sondern hängt von den Umständen des Einzelfalles ab. Dazu gehören insbesondere die Bekanntheit des Wortes als geografische Angabe und als Marke, tatsächliche oder naheliegende Beziehungen zwischen dieser und zusätzlichen Angaben, welche die Täuschungsgefahr erhöhen oder beseitigen können (Urteil 4A.8/1994 vom 25. August 1995, E. 2b, publ. in: PMMBl 1996 I S. 251; Willi, MSchG: Markenschutzgesetz, Zürich 2002, N. 227 zu Art. 2 MSchG). Entscheidend ist, ob eine Marke beim Publikum eine Ideenverbindung zu einer bestimmten Gegend oder einem bestimmten Ort hervorruft und so mindestens indirekt die Vorstellung einer Herkunftsangabe weckt (Willi, a.a.O., N. 226 zu Art. 2 MSchG; David, Basler Kommentar, N. 63 zu Art. 2 MSchG; Marbach, SIWR, Bd. III, Kennzeichenrecht, S. 72 ff.). In solchen Fällen besteht die Gefahr der Irreführung, falls die mit dem Zeichen versehenen Waren nicht dort hergestellt werden (<ref-ruling> E. 2.2 mit Hinweis).
2.2 Die Vorinstanz hat die Ansicht der Beschwerdegegnerin zu Recht verworfen, wonach die Wort-/Bildmarke COLORADO vom schweizerischen Publikum überwiegend als Fantasiezeichen verstanden werde. Sie hat zutreffend dargelegt, dass sowohl der Bundesstaat im mittleren Westen der USA mit der Hauptstadt Denver und seinen in den Rocky Mountains gelegenen Skistationen (z.B. Aspen) wie auch der Colorado River, der das Colorado-Plateau in der weltbekannten Schlucht des Grand Canyon durchquert, in der Schweiz als touristische Destinationen bekannt und beliebt sind. Angesichts der Fläche von rund 270'000 km2 und der ca. 4,3 Millionen Einwohner des US-Bundesstaates ist mit der Vorinstanz ausserdem davon auszugehen, dass Colorado nicht nur touristische Dienstleister, sondern auch industrielle Produzenten aufweist. Der Vorinstanz ist überdies beizupflichten, dass der Bildbestandteil der beanspruchten Marke deren geografischen Charakter noch verstärkt, da die hintereinander gestellten Dreieck-Formen, die von einem Kreissegment überdeckt werden, naheliegend als Berge interpretiert werden, die zusammen mit dem Wortbestandteil COLORADO die Assoziation zu den Rocky Mountains wecken. Der Schluss der Vorinstanz, dass die von der Beschwerdegegnerin beanspruchte Wort-/Bildmarke nach dem Gesamteindruck, den sie bei den Adressaten in der Schweiz hervorruft, als Hinweis auf den Bundesstaat Colorado im mittleren Westen der USA verstanden wird, ist zutreffend. Es besteht daher die Gefahr der Irreführung, falls die mit dem Zeichen versehenen Waren nicht dort hergestellt werden.
2.3 Das IGE begegnet der Gefahr der Irreführung der schweizerischen Markenadressaten in seiner bisherigen Praxis dadurch, dass es Zeichen mit geografischem Hinweis als Marken nur für Waren registriert, für deren geografische Herkunft der Hinweis wahr ist. Das beschwerdeführende Departement will in diesem Sinne die Eintragung einschränken auf Waren US-amerikanischer Herkunft. Die Vorinstanz hat im angefochtenen Entscheid diese Praxis als unverhältnismässig erachtet und dafürgehalten, sie sei zu ändern.
3. Herkunftsangaben sind nach Art. 47 Abs. 1 MSchG direkte oder indirekte Hinweise auf die geografische Herkunft von Waren oder Dienstleistungen, einschliesslich Hinweisen auf die Beschaffenheit oder Eigenschaften, die mit der Herkunft zusammenhängen. Der Gebrauch unzutreffender Herkunftsangaben ist unzulässig; ebenso der Gebrauch von Bezeichnungen, die mit einer unzutreffenden Herkunftsangabe verwechselbar sind, und von Namen, Adressen oder Marken im Zusammenhang mit Waren oder Dienstleistungen fremder Herkunft, wenn sich daraus eine Täuschungsgefahr ergibt (Art. 47 Abs. 3 MSchG).
3.1 Im Unterschied zum alten Gesetz gilt nach der Definition des geltenden Art. 47 MSchG jede Angabe als Herkunftsangabe, die direkt oder indirekt als Hinweis auf die geografische Herkunft eines Produkts verstanden wird, und zwar ohne Rücksicht darauf, ob die geografische Herkunft dem bezeichneten Produkt einen bestimmten Ruf verleiht (Botschaft des Bundesrates vom 21. November 1990, BBl 1991 I 38 f.; David, Basler Kommentar, N. 6 zu Art. 47 MSchG; Meisser/Aschmann, SIWR, Bd. III/2, Kennzeichenrecht, 2. Aufl. 2005, Herkunftsangaben und andere geographische Bezeichnungen, S. 273; Willi, a.a.O., N. 1 zu Art. 47 MSchG; Glaus, Alle geographischen Herkunftsangaben sind schützenswert, Binsenwahrheiten des Immaterialgüterrechts, Festschrift für Lucas David, Zürich 1996, S. 89; Lorenz Hirt, Der Schutz schweizerischer Herkunftsangaben, Diss. Bern 2003, S. 9 f.; Simon Holzer, Geschützte Ursprungsbezeichnungen [GUB] und geschützte geographische Angaben [GGA] landwirtschaftlicher Erzeugnisse, Bern 2005, S. 10). Der Verkehr soll vor täuschenden oder irreführenden Erwartungen über die geografische Herkunft bewahrt werden, auch wenn damit keine bestimmten Erwartungen an Qualität, Eigenschaften oder Wertschätzung der gekennzeichneten Produkte geweckt werden (Willi, a.a.O., N. 5 vor Art. 47 MSchG; Hirt, a.a.O., S. 38 ff.; Meisser/Aschmann, a.a.O., S. 157; Glaus, a.a.O., S. 91). Das geltende Recht unterscheidet sich durch den Umstand, dass Herkunftsangaben unbesehen ihres Einflusses auf die bezeichneten Produkte geschützt sind, nicht nur vom aMSchG, sondern auch von ausländischen Regelungen sowie von Sonderschutzbestimmungen in anderen Erlassen (vgl. dazu Meisser/Aschmann, a.a.O., S. 159 f.). Die Beurteilungskriterien für die Gefahr der Täuschung oder Irreführung über die geografische Herkunft sind weitgehend dieselben, die für das Irreführungsverbot gemäss Art. 2 lit. c MSchG gelten (David, a.a.O., N. 5 zu Art. 47, N. 62 ff. zu Art. 2 MSchG; Marbach, a.a.O., S. 72 ff.; Hirt, a.a.O., S. 91).
3.2 Die Vorinstanz stellt in Frage, ob die Einschränkung der Waren- oder Dienstleistungsliste auf Produkte, für welche die erwartete geografische Herkunft zutrifft, ein geeignetes Mittel sei, den Gebrauch täuschender geografischer Herkunftsangaben zu verhindern. Sie weist zwar zutreffend darauf hin, dass den Registerbehörden jede Einwirkungsmöglichkeit auf den Gebrauch der Marke fehlt. Sie verkennt jedoch, dass nicht allein der Gebrauch von Zeichen mit täuschenden Angaben über die geografische Herkunft verboten ist (Art. 47 MSchG), sondern dass solche Zeichen schon vom Markenschutz absolut ausgeschlossen sind (Art. 2 lit. c MSchG) und daher nicht ins Register eingetragen werden dürfen (Art. 30 Abs. 2 lit. c MSchG). Dass grundsätzlich die Einschränkung der im Register eingetragenen Warenliste ein geeignetes Mittel zur Durchsetzung des Verbotes der Registrierung von Zeichen ist, die vom Markenschutz absolut ausgeschlossen sind, wird nicht nur in der im angefochtenen Entscheid zitierten Literatur anerkannt, sondern ergibt sich auch daraus, dass die Vorinstanz selbst die bisherige Einschränkungspraxis unter bestimmten Voraussetzungen beibehalten will, in denen sie ein qualifiziertes Schutzbedürfnis anerkennt. Die Einschränkung ist für die Durchsetzung des Verbots der Registrierung irreführender, vom Markenschutz absolut ausgeschlossener Zeichen erforderlich; mit der von der Vorinstanz als milderes Mittel befürworteten unbeschränkten Eintragung für Waren auch anderer geografischer Herkunft bleibt Art. 30 Abs. 2 lit. c MSchG unbeachtet. Die Einschränkung der Warenliste ist entgegen der Ansicht der Vorinstanz verhältnismässig. Aus der Feststellung, dass das schweizerische Publikum mit dem Zeichen eine bestimmte Erwartung geografischer Herkunft der beanspruchten Waren oder Dienstleistungen verbindet, folgt ohne weiteres, dass das Zeichen für Produkte anderer Herkunft irreführend ist (vgl. oben E. 2.1).
Soweit die Vorinstanz aus Art. 48 MSchG ableiten wollte, die Umstände für die Erwartungen des Publikums an die geografische Herkunft ergäben sich (erst) aus dem Gebrauch der Marke, kann ihr nicht gefolgt werden. Die in Art. 48 MSchG genannten Kriterien konkretisieren vielmehr auch für die Beurteilung des Schutzausschlussgrundes von Art. 2 lit. c MSchG die Erwartungen, die nach allgemeiner Lebenserfahrung die geografische Herkunft von Waren bestimmen. Auf der - durch keine tatsächlichen Erhebungen widerlegten - allgemeinen Lebenserfahrung beruht auch die ständige Praxis, wonach ohne besondere Umstände eine geografische Bezeichnung vom schweizerischen Publikum auf das Land, nicht auf eine eingeschränkte Gegend im Ausland, bezogen wird (BGE <ref-ruling> E. 2a S. 330; kritisch Meisser/Aschmann, a.a.O., S. 282).
3.3 Die Vorinstanz anerkennt die bisherige Einschränkungspraxis für Fälle, in denen ein qualifiziertes Schutzbedürfnis der Herkunftsangabe besteht. Eine Einschränkung auf Waren der angegebenen geografischen Herkunft hält sie für gerechtfertigt, wenn
- eine Marke mit geografischem Inhalt für Bodenprodukte bestimmt ist,
- eine Marke mit geografischem Inhalt für Waren oder Dienstleistungen bestimmt ist, für welche der betreffende Ort nach Auffassung des schweizerischen Publikums einen besonderen Ruf geniesst,
- die in einer Marke enthaltene geografische Angabe auf einer Namensliste figuriert, die auf Grund zwei- oder mehrseitiger Abkommen über den Schutz von Herkunftsangaben, Ursprungsbezeichnungen oder anderen geografischen Bezeichnungen für die Schweiz verbindlich ist, oder
- eine Marke die Bezeichnung eines Staates in substantivischer oder adjektivischer Form oder dessen Wappen, Flagge oder andere staatliche Hoheitszeichen im Sinne von Art. 6ter der Pariser Verbandsübereinkunft (SR 0.232.04) enthält.
3.4 Die Vorinstanz begründet im angefochtenen Urteil ihre Ansicht nicht, weshalb sie in diesen Fällen die Täuschungsgefahr im Unterschied zu anderen unwahren Angaben über die geografische Herkunft bejaht. Soweit sich aus der Umschreibung ergibt, dass die Vorinstanz den Schutz geografischer Herkunftsangaben auf Fälle beschränken will, in denen die geografische Angabe den Ruf, die Wertschätzung oder die erwarteten Eigenschaften des Produktes beeinflusst, kann ihr nach geltendem Recht nicht gefolgt werden (oben E. 3.1). Die Angaben über die geografische Herkunft müssen nach geltendem Recht wahr sein ohne Rücksicht darauf, ob sie einen Einfluss auf die Qualitätserwartungen der Adressaten an die gekennzeichneten Produkte haben. Der gesetzgeberische Wille, der in Art. 47 MSchG zum Ausdruck gebracht wird, dem die bisherige Praxis des Bundesgerichts entspricht und der in der herrschenden Lehre nicht kritisiert wird, wird in der Registerpraxis mit der Einschränkung der Warenliste durchgesetzt. Deren Einschränkung auf qualitätsbestimmende Herkunftsangaben rechtfertigt sich auch nicht wegen allfälliger praktischer Probleme bei der Bestimmung der tatsächlichen geografischen Herkunft im Einzelfall, die im angefochtenen Entscheid wohl überzeichnet und ausserdem mit der befürworteten Einschränkung auf bestimmte, den Ruf beeinflussende geografische Angaben nicht behoben werden.
4. Eine Änderung der Praxis lässt sich regelmässig nur begründen, wenn die neue Lösung besserer Erkenntnis der ratio legis, veränderten äusseren Verhältnissen oder gewandelter Rechtsanschauung entspricht; andernfalls ist die bisherige Praxis beizubehalten (<ref-ruling> E. 3a mit Verweisen). Die Voraussetzungen für eine Praxisänderung sind vorliegend nicht erfüllt. Die ratio legis des Schutzes geografischer Herkunftsangaben liegt unverändert im Schutz des Publikums vor einer Täuschung über die geografische Herkunft der Waren, wobei nach dem geltenden Art. 47 MSchG ohne Bedeutung ist, ob die geografische Herkunft den Ruf, die Eigenschaften oder die Wertschätzung der gekennzeichneten Ware beeinflusst. Vom Markenschutz absolut ausgeschlossen sind gemäss Art. 2 lit. c MSchG insbesondere Zeichen, die täuschende Angaben über die geografische Herkunft der gekennzeichneten Waren enthalten; sie dürfen nach Art. 30 Abs. 2 lit. c MSchG nicht ins Markenregister eingetragen werden. Zur Beachtung dieser Vorschrift ist die Einschränkung des Markenschutzes auf Waren, für welche die im Zeichen angegebene geografische Herkunft zutrifft, erforderlich und verhältnismässig. Für eine Veränderung der äusseren Verhältnisse oder der Rechtsanschauung seit dem Erlass des geltenden Markenschutzgesetzes im Jahre 1992 bestehen keine Anhaltspunkte und es werden im angefochtenen Entscheid auch keine Umstände aufgeführt, die auf eine solche Veränderung hindeuten könnten. Im Übrigen hat die Vorinstanz zutreffend erwogen, dass die Wort-/Bildmarke COLORADO vom schweizerischen Publikum als Angabe der geografischen Herkunft der Waren verstanden wird, für welche die Beschwerdegegnerin Markenschutz beansprucht. Es kann ihr dagegen nicht gefolgt werden, wenn sie die Einschränkung des Markenschutzes auf Waren, für welche die geografische Herkunftsangabe tatsächlich zutrifft, für rechtswidrig erklärt. Das beschwerdeführende Departement beantragt zu Recht die Einschränkung der Eintragung im Register auf Waren, für welche die geografische Herkunftsangabe zutrifft, weil sie entsprechend den Erwartungen des schweizerischen Publikums aus den USA stammen.
5. Aus diesen Gründen ist die Verwaltungsgerichtsbeschwerde gutzuheissen.
Dem Verfahrensausgang entsprechend ist die Gerichtsgebühr der Beschwerdegegnerin aufzuerlegen (Art. 156 Abs. 1 OG). Der Beschwerdeführerin ist keine Parteientschädigung zuzusprechen (Art. 159 Abs. 2 OG).

Demnach erkennt das Bundesgericht:
1. Die Verwaltungsgerichtsbeschwerde wird gutgeheissen, der Entscheid der Eidgenössischen Rekurskommission für geistiges Eigentum vom 5. Mai 2006 wird aufgehoben und das IGE wird angewiesen, das Markeneintragungsgesuch Nr. 52266/2004 Colorado (fig.) für Waren der Klassen 18 und 25 zuzulassen mit folgender Einschränkung: "Alle vorgenannten Waren US-amerikanischer Herkunft."
2. Die Gerichtsgebühr von Fr. 2'000.-- wird der Beschwerdegegnerin auferlegt.
3. Dieses Urteil wird den Parteien und der Eidgenössischen Rekurskommission für Geistiges Eigentum schriftlich mitgeteilt.
Lausanne, 8. September 2006
Im Namen der I. Zivilabteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: