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.