Sachverhalt:
A. Die X._ Inc. (Beschwerdegegnerin) ersuchte das Eidgenössische Institut für Geistiges Eigentum (IGE; Beschwerdeführer) am 10. Dezember 2010 um Eintragung der Wortmarke "WILSON", die für "Tabak, Produkte aus Tabak, insbesondere Zigaretten; Raucherartikel; Anzünder/Feuerzeug; Streichhölzer; Aschenbecher" der Klasse 34 beansprucht wird (Gesuch CH Nr. xxx).
Am 15. Februar 2011 beanstandete das IGE das angemeldete Zeichen. Es vertrat die Auffassung, das Zeichen sei direkt beschreibend für die Warenherkunft. Es sei daher als nicht unterscheidungskräftiges sowie freihaltbedürftiges Zeichen dem Gemeingut zuzuordnen. Überdies sei das Zeichen irreführend, weil die Gefahr bestehe, dass es die Abnehmer über die Herkunft der beanspruchten Waren täusche.
Mit Schreiben vom 7. März 2011 bestritt dies die Beschwerdegegnerin, worauf das IGE mit Schreiben vom 7. Juni 2011 an seinen Beanstandungen festhielt.
Mit E-Mail vom 8. August 2011 beharrte die Beschwerdegegnerin auf ihrem Standpunkt. Sie forderte überdies Gleichbehandlung, namentlich mit der Marke "Winston", die ebenfalls dem Namen einer Stadt in North Carolina, USA, entspreche und eingetragen worden sei, obwohl die Waren in der Schweiz produziert würden.
Mit Verfügung vom 21. November 2011 verweigerte das IGE dem Markeneintragungsgesuch CH Nr. xxx WILSON für die beanspruchten Waren der Klasse 34 den Markenschutz gestützt auf Art. 2 lit. a und c MSchG.
B. Gegen diese Verfügung gelangte die Beschwerdegegnerin an das Bundesverwaltungsgericht und beantragte, die Marke ins Markenregister einzutragen. Mit Urteil vom 16. November 2012 hiess das Bundesverwaltungsgericht die Beschwerde gut, hob die Verfügung des IGE auf und wies dieses an, der Marke CH Nr. xxx WILSON für die beanspruchten Waren vollumfänglich Schutz zu gewähren.
C. Das IGE beantragt mit Beschwerde in Zivilsachen, das Urteil des Bundesverwaltungsgerichts vom 16. November 2012 aufzuheben. Das Markeneintragungsgesuch CH Nr. xxx WILSON sei für sämtliche beanspruchten Waren zurückzuweisen.
Die Beschwerdegegnerin beantragt, die Beschwerde abzuweisen. Das IGE sei anzuweisen, das Markeneintragungsgesuch CH Nr. xxx unverzüglich einzutragen. Eventualiter sei die Sache zur Neubeurteilung bzw. zur Behandlung der nicht geprüften Punkte (Gleichbehandlung) an die Vorinstanz zurückzuweisen. Die Vorinstanz schliesst auf Abweisung der Beschwerde.
Die Parteien reichten Replik und Duplik ein.
Mit Präsidialverfügung vom 22. Februar 2013 wurde der Beschwerde die aufschiebende Wirkung erteilt.

Erwägungen:
1. In der vorliegenden Registersache ist nach Art. 72 Abs. 2 lit. b Ziff. 2 BGG die Beschwerde in Zivilsachen das zulässige Rechtsmittel. Als Vorinstanz hat das Bundesverwaltungsgericht entschieden (<ref-law>). Der Entscheid erging nicht im Rahmen des Widerspruchsverfahrens (<ref-law>). Der angefochtene Entscheid schliesst das Verfahren betreffend das Markeneintragungsgesuch CH Nr. xxx WILSON ab und ist demnach als Endentscheid zu qualifizieren (<ref-law>). Der für die Beschwerde in Zivilsachen erforderliche Streitwert ist - entgegen der Meinung der Beschwerdegegnerin - als erreicht zu betrachten (<ref-law>; <ref-ruling> E. 3 S. 491 f.). Nach <ref-law> steht das Beschwerderecht namentlich in Markenregistersachen (Art. 72 Abs. 2 lit. b Ziff. 2 BGG) auch den Departementen des Bundes oder, soweit das Bundesrecht es vorsieht, den ihnen unterstellten Dienststellen zu, wenn der angefochtene Entscheid die Bundesgesetzgebung in ihrem Aufgabenbereich verletzen kann. Art. 29 Abs. 3 der Organisationsverordnung vom 17. November 1999 für das Eidgenössische Justiz- und Polizeidepartement (SR 172.213.1) sieht vor, dass das IGE in seinem Zuständigkeitsbereich zur Beschwerde an das Bundesgericht berechtigt ist. Die Registrierung von Marken gehört zum Zuständigkeitsbereich des IGE (Art. 2 Abs. 1 lit. b des Bundesgesetzes vom 24. März 1995 über Statut und Aufgaben des Eidgenössischen Instituts für Geistiges Eigentum [IGEG, SR 172.010.31]), weshalb es zur Beschwerde legitimiert ist. Die Beschwerdefrist von 30 Tagen (<ref-law>) wurde eingehalten. Auf die Beschwerde ist demnach einzutreten.
2. 2.1 Nach <ref-law> sind Zeichen vom Markenschutz ausgeschlossen, die Gemeingut sind, es sei denn, dass sie sich als Marke für die Waren oder Dienstleistungen durchgesetzt haben, für die sie beansprucht werden.
Die Gründe für den Schutzausschluss von Zeichen, die dem Gemeingut angehören, liegen entweder im Freihaltebedürfnis oder in der fehlenden Unterscheidungskraft, wobei sich Überschneidungen ergeben können (<ref-ruling> E. 4.1 S. 126; vgl. auch die Urteile 4A_619/2012 vom 7. März 2013 E. 2, zur Publikation vorgesehen; 4A_648/2010 vom 28. Februar 2011 E. 3.4, sic! 7-8/2011 S. 437 ff. und <ref-ruling> E. 3a S. 324 f.; EUGEN MARBACH, Markenrecht, in: SIWR Bd. III/1, 2. Aufl. 2009, S. 75 f. Rz. 246 ff.; DAVID ASCHMANN, in: Noth/Bühler/Thouvenin [Hrsg.], Markenschutzgesetz, Bern 2009, N. 1 zu <ref-law>; LUCAS DAVID, Basler Kommentar, Markenschutzgesetz - Muster- und Modellgesetz, 2. Aufl. 1999, N. 5 zu <ref-law>; CHRISTOPH WILLI, MSchG, Kommentar zum schweizerischen Markenrecht, Zürich 2002, N. 34 zu <ref-law>).
2.2 Als Gemeingut nach <ref-law> vom Markenschutz ausgeschlossen sind namentlich geografische Herkunftsangaben. Darunter fallen nach <ref-law> direkte oder indirekte Hinweise auf die geografische Herkunft von Waren oder Dienstleistungen, einschliesslich Hinweisen auf die Beschaffenheit oder auf Eigenschaften, die mit der Herkunft zusammenhängen. Jedem Produzenten muss es möglich sein, auf die Herkunft seiner Waren oder Dienstleistungen hinzuweisen. Herkunftsangaben gelten daher solange als freihaltebedürftig, als nicht ausgeschlossen werden kann, dass sich weitere Produzenten oder sonstige Anbieter im entsprechenden Gebiet niederlassen. Unmittelbare Herkunftsangaben, also die Namen von Städten, Ortschaften, Talschaften, Regionen, Ländern und Erdteilen bilden daher Gemeingut und sind nicht eintragungsfähig. Dies gilt nicht bloss soweit solche geografische Bezeichnungen von den massgebenden Verkehrskreisen aktuell mit der betreffenden Warengruppe in Verbindung gebracht werden können, sondern auch soweit sie künftig von den betroffenen Unternehmen als Herkunftsangabe für diese verwendet werden könnten (<ref-ruling> E. 2.1 S. 458 mit Hinweisen).
Nicht als Herkunftsangabe gelten nach <ref-law> geografische Namen und Zeichen, die von den massgebenden Verkehrskreisen nach den gesamten konkreten Umständen nicht als Hinweis auf eine bestimmte Herkunft der Waren oder Dienstleistungen verstanden werden (vgl. dazu <ref-ruling> E. 2.6; <ref-ruling> E. 2.1 S. 458 ff.). Eine Marke, die einen geografischen Namen als Bestandteil enthält oder ausschliesslich aus einem geografischen Namen besteht, der den Adressaten als solcher bekannt ist bzw. erkannt wird, verleitet den Adressaten allerdings regelmässig zur Annahme, die Ware stamme aus dem Land oder dem Ort, auf den die Angabe hinweist (<ref-ruling> E. 2.2 und 2.6.1).
2.3 Nach <ref-law> sind irreführende Zeichen vom Markenschutz absolut ausgeschlossen. 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 den Adressaten zur Annahme verleitet, die Ware stamme aus der Gegend, dem Land oder von dem Ort, auf den die Angabe hinweist, obschon das in Wirklichkeit nicht zutrifft (<ref-ruling> E. 2.1 S. 772; <ref-ruling> E. 2.2 S. 460 f.; <ref-ruling> E. 1a S. 328; je mit Hinweisen; vgl. auch <ref-ruling> E. 2.1).
2.4 Das Bundesgericht prüft grundsätzlich als Rechtsfrage frei, wie der massgebende Adressatenkreis für die beanspruchten Waren oder Dienstleistungen abzugrenzen ist und wie das allgemeine Publikum aufgrund der erwarteten Aufmerksamkeit das Zeichen wahrnimmt (<ref-ruling> E. 2.3 S. 551; <ref-ruling> E. 4 S. 347; je mit Hinweisen; vgl. auch <ref-ruling> E. 5 S. 404; <ref-ruling> E. 4b S. 317). Der massgebende Verkehrskreis kann je nach Prüfungsgesichtspunkt unterschiedlich sein. So beurteilt sich die Freihaltebedürftigkeit eines Zeichens nach dem Bedürfnis bzw. Verständnis der Konkurrenten, während bei der Beurteilung der Unterscheidungskraft auf das Verständnis des durchschnittlichen Abnehmers abzustellen ist (Urteil 4A_619/2012 vom 7. März 2013 E. 2, zur Publikation vorgesehen; MARBACH, a.a.O., S. 52 Rz. 181).
2.5 Die Vorinstanz verneinte für das Zeichen "WILSON" sowohl die Gefahr einer Irreführung (dazu Erwägung 3) als auch ein Freihaltebedürfnis (dazu Erwägung 4). Beides wird vom Beschwerdeführer als unrichtig beanstandet.
3. 3.1 Betreffend Unterscheidungskraft bzw. Irreführungsgefahr des strittigen Zeichens hielt die Vorinstanz dafür, die geografischen Bedeutungen von "Wilson" seien relativ unbekannt. Die Bezeichnung werde intuitiv als Personenname aufgefasst. Die relevanten Verkehrskreise gingen weit eher davon aus, dass eine Person mit Namen Wilson eine Tabakfabrik betreibe, so dass keine Assoziation mit einer wenig bekannten Ortschaft Wilson als Tabakanbaugebiet erfolge. Damit bestehe keine Gefahr der Irreführung.
3.2 Der Beschwerdeführer beanstandet zunächst die Definition der massgebenden Verkehrskreise.
3.2.1 Die Vorinstanz habe ausgeführt, massgebend sei die Auffassung der Endverbraucher, wenn diese die grösste Teilmenge der massgeblichen Verkehrskreise bilde. Dies verletze Bundesrecht. Nach der Rechtsprechung des Bundesgerichts genüge bei der Prüfung der Unterscheidungskraft eines Zeichens, wenn es aus Sicht nur eines der beteiligten Abnehmerkreise (Durchschnittsabnehmer oder Fachkreise) nicht schutzfähig sei. Das gelte auch bei der Beurteilung der Irreführungsgefahr. Die konkret angesprochenen Verkehrskreise müssten nicht zwingend nur Endabnehmer sein; es könne sich um die allgemeine Bevölkerung handeln oder um bestimmte Fachkreise oder Zwischenhändler. Das zahlenmässige Verhältnis der einzelnen Verkehrskreise zueinander spiele dabei keine Rolle. In der Regel dürften die Durchschnittskonsumenten die grösste Teilmenge bilden. Das von der Vorinstanz genannte Kriterium führe daher faktisch dazu, dass die Wahrnehmung der (kleineren Gruppe) der Fachkreise stets ausser Betracht bleibe.
3.2.2 Diese Kritik ist - in grundsätzlicher Hinsicht - insofern berechtigt, als die allgemeine rechtliche Erwägung der Vorinstanz, wonach für die Unterscheidungskraft die Auffassung der Endverbraucher massgebend sei, "wenn diese die grösste Teilmenge der massgeblichen Verkehrskreise bilden", in dieser Form zumindest missverständlich ist. Denn sie erweckt den Eindruck, es komme stets nur darauf an, welcher Adressatenkreis mengenmässig am grössten sei. Wäre dieses quantitative Kriterium ausschlaggebend, würde in der Tat zu allermeist allein auf das Verständnis des allgemeinen Publikums abzustellen sein, wenn dieses von den betreffenden Waren und Dienstleistungen auch angesprochen ist, und die allenfalls ebenfalls angesprochenen, aber mengenmässig kleineren Fachkreise oder weitere Adressatengruppen blieben unberücksichtigt.
3.2.3 Ob einem Zeichen markenrechtlicher Schutz zu gewähren ist, ist im Hinblick auf die konkret beanspruchten Waren oder Dienstleistungen und der davon angesprochenen Abnehmerkreise zu beurteilen (Urteil 4A_455/2008 vom 1. Dezember 2008 E. 4.3; vgl. auch <ref-ruling> E. 2.5.4 in fine/2.5.5). Die massgebenden Verkehrskreise sind demnach im Hinblick auf die tatsächlichen Abnehmer der Ware oder Dienstleistung zu definieren (Urteile 4A_492/2007 vom 14. Februar 2008 E. 3.1; 4A_116/2007 vom 27. Juni 2007 E. 6.2, nicht publ. in <ref-ruling>). Das muss nicht immer nur das allgemeine Publikum bzw. der Endabnehmer sein; auch Fachkreise oder Zwischenhändler können angesprochen werden (SIMON HOLZER, in: Noth/Bühler/ Thouvenin [Hrsg.], Markenschutzgesetz, Bern 2009, N. 21 zu <ref-law>). Bei Konsumgütern des täglichen Bedarfs ist es regelmässig der Durchschnittskonsument (WILLI, a.a.O., N. 41 zu <ref-law>).
3.2.4 Somit ist im Einzelfall zu bestimmen, an welche Abnehmerkreise sich das fragliche Produkt richtet. Dies hat die Vorinstanz getan. Sie führte aus, die von der strittigen Marke beanspruchten Waren, mithin Tabak; Produkte aus Tabak, insbesondere Zigaretten; Raucherartikel; Anzünder/Feuerzeuge; Streichhölzer; Aschenbecher, richteten sich grundsätzlich an Raucher, Tabakspezialisten und Genussraucher, die mit den Herkunftsorten und Tabaksorten besser vertraut seien als die Durchschnittsverbraucher. Sie definierte daher die massgebenden Verkehrskreise mit "Raucher, Genussraucher und Tabakspezialisten über 16 Jahren". Der Beschwerdeführer rügt nicht, dass diese auf den konkreten Fall bezogene Definition der massgebenden Verkehrskreise bundesrechtswidrig wäre. Solches ist denn auch nicht ersichtlich. Es hat daher dabei sein Bewenden. Zu präzisieren ist noch, dass es auf das Verständnis der entsprechenden schweizerischen Verkehrskreise ankommt, auch wenn eine ausländische geografische Angabe zu beurteilen ist (HOLZER, a.a.O., N. 19 zu <ref-law>; vgl. dazu auch <ref-ruling> E. 2.3 S. 419 und E. 2.6.1).
3.3 Der Beschwerdeführer kritisiert sodann die vorinstanzlichen Erwägungen zur (verneinten) Qualifikation des strittigen Zeichens als Herkunftsangabe.
3.3.1 Er macht geltend, die Vorinstanz vermische die zwei Fragen der Bekanntheit des geografischen Namens und eines weiteren Sinngehalts. Wenn die geografische Bedeutung unbekannt sei, erübrige sich die Prüfung der Mehrdeutigkeit, da in diesem Fall der geografische Sinngehalt eben nicht erkannt werde. Wenn hingegen die Bekanntheit der geografischen Bedeutung bejaht werde - wie vorliegend bei den Fachkreisen -, seien keine Gründe ersichtlich, weshalb der nicht geografische Sinngehalt, in casu die Bedeutung als Personenname, im Vordergrund stehen sollte. Sodann entspreche es nach der bundesgerichtlichen Rechtsprechung einem Erfahrungssatz, dass eine geografische Angabe als Herkunftsbezeichnung aufgefasst werde (<ref-ruling> E. 2.2). Die Vorinstanz missachte diesen Grundsatz, indem sie ausführe: "Bei Marken, die mit geografischen Bezeichnungen assoziiert werden, bedarf es somit konkreter Anhaltspunkte dafür, dass dieser Sinngehalt im Gesamteindruck des Zeichens und im Zusammenhang mit den Waren und Dienstleistungen, für die die Marke beansprucht wird, tatsächlich als Herkunftsbezeichnung verstanden wird [...] und von keinem naheliegenden Sinngehalt ohne geografischen Bezug in den Hintergrund gerückt wird." Erstens brauche es aufgrund des bundesgerichtlich anerkannten Erfahrungssatzes keine konkreten Anhaltspunkte, damit ein geografischer Name als Herkunftsangabe verstanden werde. Zweitens widerspreche es der höchstrichterlichen Rechtsprechung, bei mehrdeutigen Zeichen Anhaltspunkte dafür zu verlangen, dass die geografische Bedeutung nicht verdrängt werde.
3.3.2 Auch diese Vorbringen treffen in grundsätzlicher Hinsicht zu.
So hält der Beschwerdeführer richtig fest, dass nach der Rechtsprechung des Bundesgerichts bei einem Zeichen, das einen (bekannten) geografischen Namen enthält oder ausschliesslich aus einem solchen besteht, im Sinne eines allgemeinen Erfahrungssatzes zu vermuten ist, dass die massgebenden Verkehrskreise das Zeichen als Herkunftsangabe auffassen. Eine dem Käufer der damit bezeichneten Ware als solche bekannte geografische Angabe weckt bei diesem nach der allgemeinen Lebenserfahrung die Vorstellung, das betreffende Erzeugnis stamme aus dem Ort, auf den die Angabe hinweist (<ref-ruling> E. 2.2 und 2.6.1; so schon <ref-ruling> E. 3; ferner etwa Urteile 4A_434/2009 vom 30. November 2009 E. 3.1, in: sic! 3/2010 S. 162; 4A_324/2009 vom 8. Oktober 2009 E. 3, in: sic! 2/2010 S. 91). Es brauchen mithin entgegen der allgemeinen Erwägung der Vorinstanz keine besonderen Anhaltspunkte vorzuliegen, damit ein herkunftsbezogenes Verständnis einer (bekannten) geografischen Angabe anzunehmen ist. Umgekehrt ist nicht ausgeschlossen, dass bei mehrdeutigen Begriffen dargetan werden kann, dass ein anderer Sinngehalt, beispielsweise derjenige eines Personennamens, die geografische Bedeutung dominiert, diese mithin klar in den Hintergrund tritt, so dass deshalb keine Herkunftserwartung assoziiert wird (vgl. <ref-ruling> E. 2.3).
3.3.3 Im vorliegenden Fall ändern diese Klarstellungen indessen nichts am Ergebnis der vorinstanzlichen Beurteilung des konkreten Falles. Denn es geht in einem ersten Schritt darum abzuklären, ob die massgebenden Verkehrskreise das Wort "Wilson" - ungeachtet seiner objektiv gegebenen Bedeutung als Name einer Stadt in North Carolina/USA - überhaupt als geografische Angabe erkennen bzw. ob ihnen diese geografische Bedeutung bekannt ist, scheiden doch Namen von Städten, Ortschaften etc., die den massgebenden Verkehrskreisen nicht bekannt sind, als Herkunftsangaben aus (<ref-ruling> E. 2.6.1; <ref-ruling> E. 2.1.1).
Die Vorinstanz gelangte betreffend diese Frage zum Schluss, es könne davon ausgegangen werden, dass die relevanten Verkehrskreise die Stadt "Wilson" nicht kennen. Sie führte gestützt auf die Internetseite "www.cigarre.org/tabakanbau-usa/" aus, die geografische Bezeichnung beziehe sich auf die Stadt Wilson in North Carolina/USA, der Hauptstadt des Bezirks Wilson County. Es handle sich dabei um eines der wichtigsten Tabakanbaugebiete der USA, was Kennern bekannt sein dürfte, wohl aber nicht dem Durchschnittskonsumenten. Die Stadt, die rund 50'000 Einwohner zähle, sei insofern unter Rauchern bekannt geworden, als einer ihrer Bürger, A._, seine eigene in Ägypten produzierte und hauptsächlich für den Export bestimmte Zigarettenmarke nach ihr benannt habe (www.A.com).
Gestützt auf diese Ausführungen behauptet der Beschwerdeführer, die Bekanntheit der geografischen Angabe bei den Fachkreisen stehe fest. Diese Behauptung beruht indessen auf einem unzutreffenden Verständnis des angefochtenen Urteils. Der Beschwerdeführer deutet die erwähnte Erwägung der Vorinstanz unzutreffend, wenn er daraus ableitet, die Vorinstanz habe angenommen, der geografische Namen sei bei den Fachkreisen für Tabak und Tabakerzeugnisse bekannt. Wie die Vorinstanz in ihrer Vernehmlassung (zu der sich der Beschwerdeführer geäussert hat) klarstellte, bezieht sich die Erwägung, "Kennern" dürfte im Unterschied zu Durchschnittskonsumenten das amerikanische Tabakanbaugebiet Wilson County bekannt sein, nicht auf den ganzen Verkehrskreis der "Fachleute". Selbst unter schweizerischen Importeuren und Zwischenhändlern könnten solche qualifizierte geografische Kenntnisse nicht vorausgesetzt werden. Aus dem Urteil gehe vielmehr hervor, dass sich solche "Kenner" auf einen kleinen und nicht massgeblichen Kreis beschränkten. Der Beschwerdeführer hat dem in der Replik nicht widersprochen. Wie die Beschwerdegegnerin im Übrigen zutreffend bemerkt, wird auf der von der Vorinstanz erwähnten Internetseite über den Tabakanbau in den USA weder die Stadt Wilson noch Wilson County erwähnt. Vielmehr ist allgemein von North Carolina die Rede. Es ist daher schon kaum belegt, dass es sich bei Wilson County "um eines der wichtigsten Tabakanbaugebiete der USA" handle. Die vorinstanzliche Aussage, dass dieses bei "Kennern" bekannt sein dürfte, lässt sich daher zwangslos auf die nachfolgenden Hinweise auf die von A._, einem Bürger von Wilson, danach benannte Zigarettenmarke beziehen. Damit schränkt sich aber der Kreis von "Kennern", denen "Wilson" als geografische Angabe bekannt ist, derart ein, dass er nicht massgebend sein kann.
Insofern lässt sich im Übrigen auch die - vom Beschwerdeführer kritisierte und in der Tat etwas unpräzise - Formulierung der Vorinstanz in der Zusammenfassung (E. 5.5) erklären, wonach die geografischen Bedeutungen von "Wilson" relativ unbekannt seien. Sie wollte damit andeuten, dass es immerhin einige wenige, hier aber nicht zu berücksichtigende Kenner der geografischen Bedeutungen von "Wilson" gebe.
Abzustellen ist auf die von der Vorinstanz andernorts (E. 5.2 in fine) klar festgehaltene Annahme, dass die relevanten Verkehrskreise in der Schweiz die Stadt "Wilson" nicht kennen. Der Beschwerdeführer hat dies nicht widerlegt und bringt auch sonst nichts vor, das eine gegenteilige Annahme zu begründen vermöchte.
3.3.4 Es ist demnach davon auszugehen, dass das Wort "Wilson" den relevanten Verkehrskreisen in der Schweiz nicht im Sinne einer geografischen Angabe als Name für die Stadt in North Carolina bekannt ist. Damit ist der Ausgang des Rechtsstreits besiegelt, ohne dass nach weiteren Sinngehalten und ihrer allfälligen Dominanz geforscht werden müsste. Wenn "Wilson" als Name für die Stadt in North Carolina den massgebenden Verkehrskreisen nicht bekannt ist, entfällt folgerichtig von vornherein eine herkunftsbezogene Assoziation, und entsprechend besteht keine Irreführungsgefahr über die Herkunft der mit WILSON zu bezeichnenden Waren im Sinne von <ref-law>. Eine solche hat die Vorinstanz mithin zu Recht verneint.
3.3.5 Aus dem gleichen Grund - mangelnde Bekanntheit der geografischen Bedeutung bei den massgebenden Verkehrskreisen - ist auch die Unterscheidungskraft gegeben. Das Zeichen ist nicht beschreibend hinsichtlich der Herkunft der Waren und zählt daher insofern nicht zum Gemeingut gemäss <ref-law>.
4. 4.1 Grundsätzlich sind direkte Herkunftsangaben freihaltebedürftig, da es jedem (aktuellen und künftigen) Konkurrenten möglich sein muss, auf die Herkunft seiner Waren oder Dienstleistungen hinzuweisen; dabei soll er nicht durch Marken anderer Konkurrenten behindert werden. Für die Bejahung eines Freihaltebedürfnisses muss es immerhin realistisch erscheinen, dass sich im betreffenden Gebiet ein Produzent niederlassen könnte, und die Bezeichnung demnach für die beanspruchten Waren ernsthaft als geografische Herkunftsangabe in Betracht fällt (<ref-ruling> E. 2.1 S. 458; Urteil 4A_434/2009 vom 30. November 2009 E. 3.1, sic! 3/2010 S. 162 ff.; MARBACH, a.a.O., S. 122 Rz. 392). Für ausländische Herkunftsangaben entfällt ein Freihaltebedürfnis, wenn das Zeichen im betreffenden Herkunftsland selbst nur einem Anbieter vorbehalten ist, insbesondere weil es als Marke für gleiche Waren oder Dienstleistungen eingetragen wurde (BGE <ref-ruling> E. 2b S. 330 f.; MARBACH, a.a.O., S. 122 f. Rz. 394).
4.2 Die Vorinstanz erwog, die Wortmarke "WILSON" für Tabakwaren sei in den USA nicht registriert. Hingegen sei für die Zigarettenmarke "Wilson" in den USA eine Wort-/Bildmarke Nr. 2,007,845 in der Nizza-Klasse 34 registriert. Insgesamt genössen rund 25 Marken mit dem Wortlaut "Wilson", davon acht Wortmarken, Schutz in den USA. Die Vorinstanz verneinte ein Freihaltebedürfnis an der Bezeichnung "Wilson" mit dem Argument, dass durch das Vorhandensein mehrerer Wortmarken für Industrieprodukte, die in Wilson, North Carolina, hergestellt werden könnten (z.B. Stoffmesser, Signalverstärker und Gelatine) sowie einer Wort-/Bildmarke für Tabakwaren ausreichend Indizien bestünden, dass "Wilson" selbst in den USA mehrheitlich als Eigen- und nicht als Ortsname aufgefasst werde. Dies gelte offensichtlich selbst dann, wenn der Markeninhaber offenlege, dass er tatsächlich auf die Eigenschaft von Wilson als Tabakanbauort Bezug nehme (so Dr. A._ auf www.A.com). Wenn aber in den USA weder eine absolute noch eine relative Freihaltebedürftigkeit für "Wilson" bestehe, entfalle auch das Freihaltebedürfnis für die Schweiz.
4.3 Der Beschwerdeführer hält dies für unzulässig. Denn eine Wortmarke "WILSON" für identische Waren sei in den USA nicht registriert.
Er führt aus, bei der Prüfung des Freihaltebedürfnisses sei zu fragen, ob Konkurrenten zur Bezeichnung der beanspruchten Waren auf die ungehinderte Verwendung der Herkunftsangabe angewiesen sind. Dem ist beizupflichten, ebenso der Folgerung, dass nur in Betracht zu ziehen ist, ob das Herkunftsland ein Freihaltebedürfnis in Bezug auf identische Waren verneint hat. Der Beschwerdeführer beanstandet insofern zu Recht, dass die Vorinstanz die für andere als die hier beanspruchten Waren eingetragenen Marken "Wilson" berücksichtigt hat. Hingegen kann ihm nicht gefolgt werden, wenn er meint, dass auch die Wort-/Bildmarke Nr. 2,007,845 "WILSON", die in den USA für identische Waren (Zigaretten) der Klasse 34 registriert ist, unberücksichtigt bleiben muss. Zwar trifft es zu, dass es sich bei dieser Marke nicht um eine reine Wortmarke, sondern um eine Wort-/Bildmarke handelt. Indessen dominiert der Schriftzug WILSON als prägender Bestandteil derart, dass angenommen werden darf, die US-Markenbehörde habe die Bezeichnung "WILSON" für Zigaretten als nicht freihaltebedürftig beurteilt (vgl. dazu <ref-ruling> E. 3b/aa; <ref-ruling> E. 1 S. 66; ferner die Urteile 4A_324/2009 vom 8. Oktober 2009 E. 6, sic! 2/2010 S. 91; 4A.1/2005 vom 8. April 2005 E. 2, in: sic! 9/2005 S. 649; je mit Hinweisen). Damit scheidet ein Freihaltebedürfnis auch für die Schweiz aus.
5. Die Beschwerde ist demnach abzuweisen. Dem Beschwerdeführer sind keine Gerichtskosten aufzuerlegen (<ref-law>). Hingegen hat er der Beschwerdegegnerin für das bundesgerichtliche Verfahren eine Parteientschädigung zu entrichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Es werden keine Kosten erhoben.
3. Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 3'500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Bundesverwaltungsgericht, Abteilung II, schriftlich mitgeteilt.
Lausanne, 16. April 2013
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Widmer