Sachverhalt: A. Die X._ AG (Beschwerdeführerin) ist Inhaberin der Wortmarke Nr. 537423 "Gotthard" und der Wort/Bildmarke Nr. 539910 gemäss nachfolgender Abbildung, die im schweizerischen Markenregister u.a. für Waren der Klasse 4, insbesondere "Brennstoffe (einschliesslich Motorentreibstoffe) " eingetragen sind: Am 25. Februar 2008 erhob die Beschwerdeführerin beim Obergericht des Kantons Uri Klage gegen die Y._ AG Gotthard, Attinghausen (Beschwerdegegnerin). Sie beantragte im Wesentlichen, es sei der Beschwerdegegnerin zu verbieten, das Wort "Gotthard" als Firmenbestandteil zu benutzen, und es sei die Beschwerdegegnerin zu verpflichten, den Bestandteil "Gotthard" in ihrer Firma innert 30 Tagen im Handelsregister zu löschen. Zur Begründung führte sie im Wesentlichen an, es bestehe eine Verwechslungsgefahr zwischen ihrer im Markenregister eingetragenen Wortmarke "Gotthard" und der Firma der Beschwerdegegnerin. Am 8. April 2008 erstattete die Beschwerdegegnerin ihre Klageantwort und erhob Widerklage, wobei sie folgende Anträge stellte: "1. Die Klage sei abzuweisen und die Widerklage sei gutzuheissen. 2. Die Schweizer Wort/Bildmarken Registrierung 539 910 "GOTTHARD" und die Schweizer Wortmarke 537 423 "GOTTHARD" seien für "Brennstoffe (einschliesslich Motorentreibstoffe) " als nichtig zu erklären. 3. Das Institut für Geistiges Eigentum, Stauffacherstrasse 65/59g, 3003 Bern, sei gemäss Artikel 54 des Markenschutzgesetzes anzuweisen, die Schweizer Wort-/Bildmarke 539 910 "GOTTHARD" und die Schweizer Wortmarke 537 423 "GOTTHARD" für "Brennstoffe (einschliesslich Motorentreibstoffe) " zu löschen. 4. (...) ". Mit Urteil vom 23. Januar 2009 wies das Obergericht die Klage ab. Die Widerklage hiess es gut, soweit es darauf eintrat, und erklärte die Schweizer Wortmarke-Registrierung Nr. 537 423 "GOTTHARD" und die Schweizer Wort-/Bildmarke-Registrierung Nr. 539 910 "GOTTHARD" je für "Brennstoffe (einschliesslich Motorentreibstoffe) " gemäss Nizza Klassifikation Nr. 4 als nichtig. Zur Begründung führte es im Wesentlichen aus, das Wort "Gotthard", das auch die streitbetroffene Wort-/Bildmarke dominiere, stelle für die in Frage stehenden Waren eine zum Gemeingut gehörende Herkunftsbezeichnung dar, die nach Art. 2 lit. a MSchG vom Schutz ausgeschlossen sei. B. Die Beschwerdeführerin beantragt mit Beschwerde in Zivilsachen, das Urteil vom 23. Januar 2009 aufzuheben und die Klage vom 25. Februar 2008 gutzuheissen. Auf die Widerklage sei nicht einzutreten, eventuell sei sie abzuweisen. Eventuell sei die Sache zur Neubeurteilung von Klage und Widerklage an die Vorinstanz zurückzuweisen. Die Beschwerdegegnerin schliesst auf Abweisung der Beschwerde und Bestätigung des angefochtenen Urteils. Das Obergericht verzichtete auf eine Vernehmlassung.