Sachverhalt:
A. A.a Die Sortenorganisation Appenzeller Käse GmbH (Klägerin) ist eine Selbsthilfeorganisation zur Förderung der Qualität und des Absatzes sowie der Anpassung der Produktion von landwirtschaftlichen Erzeugnissen an die Erfordernisse des Marktes nach Art. 8 des Landwirtschaftsgesetzes (LWG; SR 910.1). Ihre rund 100 Genossenschafter sind einerseits Käsereigenossenschaften und Käse produzierende Einzelfirmen aus den Kantonen St. Gallen, Thurgau und Appenzell, anderseits Organisationen wie die in Appenzell domizilierte Stiftung Fonds für Appenzeller Käse sowie die Genossenschaft Appenzeller Käsehändler-Verband; sie gilt als Branchenorganisation im Sinne von Art. 8 Abs. 2 LWG. Sie wurde am 27. Mai 1998 im Handelsregister des Kantons Appenzell Innerrhoden eingetragen, hat ihren Sitz in Appenzell und weist ein Stammkapital von Fr. 600'000 aus; ihr Zweck besteht in der Erhaltung und Förderung von Appenzeller Käse als typische Ostschweizer Käse-Spezialität, namentlich durch eine zielgerichtete Markenpolitik, durch gemeinsames Qualitätsmanagement und gemeinsame Produktionsplanung.
Die Appenzeller Natural AG (Beklagte) wurde am 9. Februar 1996 im Handelsregister des Kantons Appenzell Ausserrhoden eingetragen. Sie hat zum Zweck den Erwerb einer Garantiemarke zur Kennzeichnung von Agrarprodukten aus dem Herkunftsgebiet "Appenzellerland" sowie die Erteilung von Bewilligungen zum Benutzen dieser Marke an Produzenten.
A.b Die Klägerin ist Inhaberin der Wort-/Bildmarke CH-Nr. 433 383 "Appenzeller® Switzerland", welche ihr Rechtsvorgänger, der Kanton Appenzell I.Rh., am 7. Dezember 1993 im schweizerischen Markenregister hatte eintragen lassen.
Die Beklagte hinterlegte am 26. Februar 1996 als Garantiemarke die Wort-/Bildmarke CH Nr.430024 "Appenzeller Natural" mit Bauernhaus und Baum in den beanspruchten Farben gelb, blau, grün und schwarz für die Waren der internationalen Klassen 29 (darunter Milch und Milchprodukte), 30 und 31 mit schweizerischer Herkunft.
Ein von der Klägerin gegen diese Hinterlegung erhobener Widerspruch wurde mit Entscheid des Instituts für Geistiges Eigentum (IGE) am 3. Dezember 1998 abgewiesen. Das IGE verneinte die Verwechslungsgefahr der beiden Marken im Wesentlichen mit der Begründung, dass sie nur im kennzeichnungsschwachen Element "Appenzeller" übereinstimmten.
B. Am 17. Oktober 2000 stellte die Klägerin beim Obergericht des Kantons Appenzell Ausserrhoden die Begehren, die CH-Marke Nr. 430 024 der Beklagten sei für den Bereich Milchprodukte nichtig zu erklären, der Beklagten sei der Gebrauch der Bezeichnung "Appenzeller Natural" für Käse zu verbieten und das Urteil sei in zwei gerichtlich zu bestimmenden Publikationsorganen zu veröffentlichen.
Mit Urteil vom 29. Januar 2002 schützte das Obergericht von Appenzell Ausserrhoden die Klage. Die CH-Marke Nr. 430 024 der Beklagten (Appenzeller Natural AG) wurde für den Bereich Milchprodukte als nichtig erklärt (Ziffer 1); den verantwortlichen Organen der Beklagten wurde unter Androhung der Straffolgen gemäss <ref-law> verboten: (a) Die Bezeichnung "Appenzeller Natural" auf Käse oder deren Verpackung anzubringen; (b) Unter dem Zeichen "Appenzeller Natural" Käse anzubieten, in Verkehr zu bringen oder zu diesem Zwecke zu lagern; (c) Unter der Bezeichnung "Appenzeller Natural" Käse zu exportieren; (d) Das Zeichen "Appenzeller Natural" im Zusammenhang mit Käse auf Geschäftspapieren, in der Werbung oder sonstwie im geschäftlichen Verkehr zu gebrauchen (Ziffer 2) und die Klägerin wurde ermächtigt, das Urteil nach Eintritt der Rechtskraft je einmal, halbseitig im (St. Galler) Tagblatt, Gesamtausgabe, und im Appenzeller Volksfreund auf Kosten der Beklagten zu publizieren (Ziffer 3).
C. Mit Berufung vom 17. Mai 2002 stellt die Beklagte die Rechtsbegehren, das Urteil des Obergerichts von Appenzell Ausserrhoden vom 29. Januar 2002 sei aufzuheben und die Klage sei vollumfänglich abzuweisen. Sie rügt die Verletzung von <ref-law>, <ref-law>, <ref-law> und <ref-law>.
Die Klägerin schliesst in ihrer Antwort auf Abweisung der Berufung.

Das Bundesgericht zieht in Erwägung:
1. Vom Markenschutz ausgeschlossen sind nach <ref-law> Zeichen, die Gemeingut sind, es sei denn, dass sie sich als Marke für die Waren oder Dienstleistungen, für die sie beansprucht werden, durchgesetzt haben.
1.1 Die Vorinstanz ist im angefochtenen Urteil zutreffend von der notorischen Tatsache ausgegangen, dass "Appenzell" als Kantons- bzw. Gemeindename die geographische Herkunft der Ware beschreibt und insofern grundsätzlich zum freihaltebedürftigen Gemeingut gehört (<ref-ruling> E. 2b S. 330; David, Markenschutzgesetz, Muster- und Modellgesetz, 2. Aufl., Basler Kommentar, N. 22 zu Art. 2 MschG; Marbach, Markenrecht, in: Schweizerisches Immaterialgüter- und Wettbewerbsrecht, Bd. III, Kennzeichenrecht, Basel 1996, S. 52 f.). Sie hat jedoch gestützt auf das Ergebnis einer fachkundigen Erhebung geschlossen, die Bezeichnung habe sich für die Waren der Klägerin, das heisst für deren Käse, bei den schweizerischen Verbrauchern durchgesetzt.
1.2 Ein Kennzeichen hat sich im Verkehr durchgesetzt, wenn es von einem erheblichen Teil der Adressaten im Wirtschaftsverkehr als Hinweis auf ein bestimmtes Unternehmen verstanden wird, ohne dass die namentliche Kenntnis dieses Unternehmens erforderlich wäre (David, a.a.O., N. 39 zu Art. 2 MschG; Marbach, a.a.O., S. 55). Die Durchsetzung als Individualzeichen muss in der gesamten Schweiz erfolgt sein; eine bloss lokale Durchsetzung genügt nicht (<ref-ruling> E. 2). Dies schliesst jedoch eine lokal unterschiedlich ausgeprägte Durchsetzung des Zeichens grundsätzlich nicht aus, sofern das Zeichen in der ganzen Schweiz von einem gewissen Teil der Adressaten als Individualzeichen verstanden wird. Wird die Verkehrsdurchsetzung durch eine fachkundige Befragung der massgebenden Verkehrskreise festgestellt, so ist zu berücksichtigen, dass erfahrungsgemäss auf abstrakte Befragung das Zeichen nur von einem Teil der Abnehmer als Marke identifiziert wird, auch wenn das Zeichen allgemein bekannt ist (Marbach, a.a.O., S. 55). Wenn daher mehr als zwei Drittel der repräsentativ Befragten ein Zeichen in bestimmter Weise zuordnen, darf nach allgemeiner Lebenserfahrung angenommen werden, dass es sich im Verkehr durchgesetzt hat.
1.3 Im vorliegenden Fall hat die Vorinstanz eine gerichtliche Expertise eingeholt. Auf die Frage, was beim Wort "Appenzeller" assoziiert werde, antworteten 70.5% der repräsentativ Befragten mit "Käse", wobei der Anteil in der Deutschschweiz bei 78,1% und in der lateinischen Schweiz bei 47,2% lag. Auf die Zusatzfrage, welche Lebensmittel mit dem Begriff "Appenzeller" in Verbindung gebracht würden, nannten 83.6% "Käse", 11.6% "Biber". Da "Appenzeller Käse" unbestritten allein von der Klägerin bzw. deren Gesellschafter produziert und vertrieben wird, hat die Vorinstanz bei dieser Sachlage die Durchsetzung der klägerischen Marke "Appenzeller®Switzerland" bei den schweizerischen Konsumentinnen und Konsumenten als Hinweis auf die Klägerin zu Recht bejaht. Sie hat in diesem Zusammenhang auch zutreffend den Markenbestandteil "Appenzeller" als charakteristisch qualifiziert. Die Behauptung der Beklagten, die klägerische Marke habe sich für Käse der Klägerin im Verkehr erst infolge verstärkter Werbeanstrengungen nach der Eintragung der Marke der Beklagten durchgesetzt, findet in den Feststellungen des angefochtenen Urteils keine Stütze. Sie hat mangels Nachweises entsprechender Behauptungen vor Vorinstanz als neu zu gelten und ist nicht zu hören (Art. 55 Abs. 1 lit. c OG).
1.4 Der Beklagten kann auch nicht gefolgt werden, wenn sie sinngemäss die Auffassung vertritt, für die Verkehrsdurchsetzung eines Zeichens sei ein langer und unangefochtener Gebrauch unabdingbare Voraussetzung. Dass sich ein Zeichen im Verkehr durchgesetzt hat, kann zwar aus dessen langem und unangefochtenem Gebrauch geschlossen werden (vgl. <ref-ruling> E. 4 S. 356). Die Durchsetzung im Verkehr als Individualzeichen setzt jedoch ein bestimmtes Verständnis des Publikums hinsichtlich der Bedeutung des Zeichens voraus. Dieses Verständnis kann auch auf andere Weise belegt werden als durch einen langen, unangefochtenen Exklusivgebrauch des Zeichens, namentlich durch eine geeignete Befragung. Zwar ist in dieser Hinsicht der Beklagten zuzugestehen, dass "Appenzell" als direkte geographische Herkunftsangabe dem schweizerischen Publikum allgemein bekannt ist, was als notorisch keines Beweises bedarf, und die Monopolisierung dieser Angabe daher insbesondere für ein landwirtschaftliches Produkt wie Käse nicht leichthin anzunehmen ist. Das Publikum bringt jedoch den Begriff "Appenzeller" mit dem von der Klägerin vertriebenen Käse in Verbindung, der nicht ausschliesslich aus dem Gebiet der beiden Appenzell stammt, sondern auch aus den Kantonen St. Gallen und Thurgau ( Anhang 1 Ziff. 1 1.1 und 1.7 zur Verordnung über die Bezeichnungen von Schweizer Käse, SR 817.141; vgl. auch David, a.a.O., N. 23 zu <ref-law>). Die Vorinstanz hat daher ohne Bundesrechtsverletzung die Verkehrsdurchsetzung der Bezeichnung "Appenzeller" für Käse der Klägerin bejaht und daher <ref-law> nicht verletzt.
2. Die Beklagte rügt eine Verletzung von <ref-law> und beanstandet, dass die Vorinstanz das Feststellungsinteresse der Klägerin bundesrechtswidrig bejaht habe.
2.1 Die Klage auf Feststellung eines dem eidgenössischen Recht unterstehenden Rechtsverhältnisses ist zuzulassen, wenn der Kläger an der sofortigen Feststellung ein schutzwürdiges Interesse hat, das rechtlicher oder tatsächlicher Natur sein kann, aber erheblich sein muss (<ref-ruling> E.2a S. 147; <ref-ruling> E. 2a S. 255). Ein schutzwürdiges Interesse an der Behandlung einer Feststellungsklage wird namentlich bejaht, wenn die Ungewissheit der Rechtsbeziehung zwischen den Parteien durch richterliche Feststellung behoben werden kann und ihre Fortdauer für den Kläger nicht zumutbar ist (<ref-ruling> E. 1a S. 51). An der Klage auf Feststellung der Nichtigkeit einer Marke hat insbesondere der besser Berechtigte im Sinne von <ref-law> ein schutzwürdiges Interesse.
2.2 Die Beklagte hält dafür, die Gutheissung der Nichtigkeitsklage - mit der Folge der Löschung des entsprechenden Registereintrags ihrer jüngeren Marke (vgl. <ref-ruling> E. 2a S. 147 f.) - würde der Klägerin nichts nützen, da sie keine Konkurrentin der Beklagten sei und durch die Garantiemarke der Beklagten nicht behindert werde. Ausserdem hält sie dafür, ein Interesse könnte die Klägerin allein an der Nichtigerklärung der Marke für Appenzeller Käse, nicht aber für sämtliche Milchprodukte haben. Sie verkennt mit diesem Vorbringen, dass das Markenrecht mit der Eintragung im Register entsteht (<ref-law>) und dem Inhaber das ausschliessliche Recht verleiht, die Marke zur Kennzeichnung der Waren oder Dienstleistungen, für die sie beansprucht wird, zu gebrauchen (Art. 13 Abs. 1 MschG) und Defensivmarken nichtig sind (<ref-ruling> E. 1). Weshalb die Beklagte mit der Eintragung der Marke im vorliegenden Fall das Gebrauchsrecht für die hinterlegte Marke nicht beanspruchen sollte, ist unerfindlich. Im angefochtenen Urteil wird denn auch festgehalten, das Verhalten der Beklagten im Prozess lasse auf eine "latente" Benützungsabsicht schliessen. Durch den Gebrauch eines gleichen oder ähnlichen Zeichens für gleiche oder gleichartige Produkte wird die Klägerin aber in ihrem eigenen Markenrecht beeinträchtigt. Sie hat aus diesem Grund ein schutzwürdiges Interesse an der Feststellung, dass die jüngere Marke der Beklagten im Sinne von <ref-law> vom Schutz ausgeschlossen ist. Ob dies zutrifft, ist materiell zu prüfen.
3. 3.1 Die Gefahr der Verwechslung im Sinne von <ref-law> besteht, wenn das jüngere Zeichen die ältere Marke in ihrer Unterscheidungsfunktion beeinträchtigt. Eine solche Beeinträchtigung ist gegeben, falls zu befürchten ist, dass die massgebenden Verkehrskreise sich durch die Ähnlichkeit des Zeichens irreführen lassen und Waren, die das eine oder das andere Zeichen tragen, dem falschen Markeninhaber zurechnen, oder falls das Publikum die Zeichen zwar auseinander zu halten vermag, aufgrund ihrer Ähnlichkeit aber falsche Zusammenhänge vermutet, insbesondere an Serienmarken denkt, welche verschiedene Produktelinien des gleichen Unternehmens oder von mehreren, wirtschaftlich verbundenen Unternehmen kennzeichnen (<ref-ruling> E. 2a). Für die Verwechselbarkeit von Marken ist der Gesamteindruck massgebend, den sie in der Erinnerung der Adressaten hinterlassen (<ref-ruling> E. 2a S. 378). Je stärker sich ein Zeichen im Verkehr durchgesetzt hat, desto grösser ist sein Schutzumfang und je näher sich die Waren sind, für welche die Marken registriert sind, desto grösser wird das Risiko von Verwechslungen und desto stärker muss sich das jüngere Zeichen vom älteren abheben, um die Verwechslungsgefahr zu bannen (<ref-ruling> E. 2a S. 385, E. 3a S. 387).
3.2 Die Vorinstanz hat der Beklagten zwar zugestanden, dass sich die beiden Marken der Parteien durch das Schriftbild, in den beiden Begriffen "Switzerland" und "Natural" sowie durch das Bildelement in der Marke der Beklagten (stilisierte Landschaft mit Haus und Baum) unterscheiden. Sie hat erwogen, dass diese Unterschiede zwar klar zutage treten, wenn die Zeichen als solche miteinander verglichen werden, dass sie aber in der Erinnerung der Adressaten nicht haften bleiben. Diese Beurteilung ist bundesrechtlich nicht zu beanstanden. Das die Erinnerung prägende Element der beiden Marken ist "Appenzeller", das angesichts der Verkehrsdurchsetzung des Zeichens für Käse als starkes Zeichen zu qualifizieren ist (<ref-ruling> E. 2a S. 385). Demgegenüber fallen das unterschiedliche Schriftbild und die für Naturprodukte beschreibende Angabe "Natural" im Vergleich zum für das schweizerische Publikum kaum aussagekräftigen Zusatz "Switzerland" für das Erinnerungsbild ebenso wenig in Betracht wie das eine bäuerliche Landschaft symbolisierende Bild eines Bauernhauses mit Baum in der Marke der Beklagten. Der Beklagten kann nicht gefolgt werden, wenn sie vorbringt, es sei das Bildelement ihrer Marke, das die Erinnerung der Adressaten präge; für Landwirtschaftsprodukte ist eine durch Wiese, Bauernhaus und Baum symbolisierte bäuerliche Landschaft in der Regel beschreibend und prägt sich jedenfalls dem Konsumenten nicht ohne weiteres ein. Auch kann dem Argument der Beklagten nicht beigepflichtet werden, dass der Konsument aufgrund der Werbung der Klägerin eine ganz andere Marke als die im Register eingetragene wahrnehme. Dass die Klägerin in der Werbung und zur näheren Bezeichnung ihrer Produkte nach dem Vorbringen der Beklagten Zusätze wie (Appenzeller) "extra", "Classic", "1⁄4 fett" und "Surchoix" verwendet, verstärkt angesichts des Markenbestandteils "Natural" der Beklagten die Gefahr der Verwechslung im Gegenteil zusätzlich, da derartige Zusatzangaben an Serien von Produkten denken lassen, die dem gleichen Hersteller zugeordnet werden.
3.3 Die Vorinstanz hat die Verwechslungsgefahr der älteren und im Verkehr durchgesetzten Marke "AppenzellerSwitzerland" der Klägerin gegenüber der jüngeren Wort-/Bildmarke "Appenzeller Natural" der Beklagten für die Ware Käse zutreffend bejaht. Bundesrechtlich nicht zu beanstanden ist aber auch, dass die Vorinstanz die Nichtigkeit der Marke der Beklagten für den gesamten Bereich der Milchprodukte festgestellt hat. Dass Produkte wie Käse, Yoghurt, Rahm, Butter und Quark aus Milch hergestellt werden, gehört zum Allgemeinwissen des schweizerischen Publikums; die Gleichartigkeit der Milchprodukte untereinander kann aus diesem Grund nicht in Abrede gestellt werden. Zur Gewährleistung der Unterscheidungsfunktion der Marke ist jedoch nach den gesamten Umständen ein hinreichender Abstand einzuhalten, wobei an die Unterschiedlichkeit der Waren umso höhere Anforderungen zu stellen sind, je weniger sich die Zeichen voneinander unterscheiden (<ref-ruling> E. 2c S. 99). Die beiden umstrittenen Zeichen stimmen wie erwähnt im das Erinnerungsbild prägenden Bestandteil "Appenzeller" überein, ohne dass die Unterschiede hinreichend im Gedächtnis haften blieben. Da sich der Begriff "Appenzeller" für Käse der Klägerin im Verkehr durchgesetzt hat und dementsprechend davon auszugehen ist, dass er als starkes Zeichen über einen grösseren Schutzumfang verfügt (<ref-ruling> E. 2a S. 385), ist die Gefahr der Verwechslung für die gleichartigen Waren der übrigen Milchprodukte von der Vorinstanz zutreffend bejaht worden.
4. Die Beklagte macht schliesslich geltend, die Klägerin habe ihren Anspruch auf Nichtigerklärung der jüngeren Marke verwirkt und handle mit der verspäteten Rechtsausübung rechtsmissbräuchlich. Die Verwirkung setzt voraus, dass der Berechtigte die Verletzung seiner Rechte durch Mitgebrauch eines gleichen oder ähnlichen Zeichens während längerer Zeit widerspruchslos geduldet und der Verletzer inzwischen am Zeichen einen eigenen wertvollen Besitzstand erworben hat (<ref-ruling> E. 4a S. 577, vgl. auch <ref-ruling> E. 4c/bb S. 364). Diese Voraussetzungen sind vorliegend schon deshalb nicht erfüllt, weil die Marke der Beklagten bisher gar nicht für Milchprodukte verwendet worden ist, wie sie andernorts selbst betont, und daher ein wertvoller Besitzstand nicht entstehen konnte. Dass schliesslich die Klägerin die Verwendung des Begriffs "Appenzeller" für die Kennzeichnung von Milchprodukten durch Dritte geduldet hätte, wird im angefochtenen Urteil nicht festgestellt. Es erübrigt sich daher, auf den diesbezüglich von der Beklagten erhobenen Vorwurf rechtsmissbräuchlichen Verhaltens einzugehen.
5. Die Berufung der Beklagten ist abzuweisen und das angefochtene Urteil zu bestätigen. Bei diesem Verfahrensausgang ist die Gerichtsgebühr der Beklagten aufzuerlegen (Art. 156 Abs. 1 OG). Sie hat überdies der anwaltlich vertretenen Klägerin eine Parteientschädigung zu zahlen (Art. 159 Abs. 1 und 2 OG).

Demnach erkennt das Bundesgericht:
1. Die Berufung wird abgewiesen und das Urteil des Obergerichts von Appenzell A.Rh., 2. Abteilung, vom 29. Januar 2002 bestätigt.
2. Die Gerichtsgebühr von Fr. 3'000.-- wird der Beklagten auferlegt.
3. Die Beklagte hat die Klägerin für das bundesgerichtliche Verfahren mit Fr. 4'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Obergericht von Appenzell A.Rh., 2. Abteilung, schriftlich mitgeteilt.
Lausanne, 21. August 2002
Im Namen der I. Zivilabteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: