Sachverhalt:
A. X._ und A._ kauften und verkauften als Geschäftsführer und je hälftig Beteiligte der B._ AG Appenzeller Käse. Die Sortenorganisation Appenzeller Käse GmbH (nachfolgend: Sortenorganisation) als Inhaberin der Marke "Appenzeller" hat die Verwendung der Appenzeller Käse-Marken in einem Markenreglement festgelegt, dessen Einhaltung sie überwacht. Sie vergibt die entsprechenden Lizenzen an die Käsehändler. Im September 2001 schloss sie einen Lizenzvertrag mit der B._ AG ab. Zwischen Mai und Dezember 2003 brachte dieses Unternehmen Etiketten, die für den sortenechten Appenzeller Käse bestimmt waren, auf Schnittkäse-Laiben an. Sie verkaufte insgesamt 27'345 kg ins Ausland, wodurch sie aufgrund des tieferen Ankaufspreises für Schnittkäse einen Mehrerlös von mindestens Fr. 76'566.-- erzielte. Im gleichen Zeitraum verkaufte die B._ AG im Inland Schnittkäse als Appenzeller Käse und generierte hierbei Mehreinnahmen von Fr. 57'266.55. Weiter erhielt sie von der Sortenorganisation Exportprämien in der Höhe von Fr. 13'672.50. Am 3. und 10. Dezember 2003 versuchte die B._ AG erneut, Schnittkäse als sortenechten Appenzeller Käse zu exportieren. Diese Käselieferungen mit einem potentiellen Mehrerlös von Fr. 13'052.20 hielten die Zollbehörden jedoch zurück.
B. Das Amtsstatthalteramt Sursee verurteilte X._ am 30. Januar 2007 wegen gewerbsmässigen Betrugs, gewerbsmässiger Warenfälschung sowie gewerbsmässigen betrügerischen Markengebrauchs zu einer Freiheitsstrafe von sechs Monaten, bedingt vollziehbar bei einer Probezeit von zwei Jahren, sowie zu einer unbedingten Geldstrafe von 130 Tagessätzen zu Fr. 150.--. A._ hatte es zuvor mittels Strafverfügung vom 1. Dezember 2006 wegen Warenfälschung und betrügerischen Markengebrauchs zu einer Gefängnisstrafe von acht Wochen, bedingt vollziehbar bei einer Probezeit von zwei Jahren, und zu einer Busse von Fr. 10'000.-- verurteilt.
X._ focht die Strafverfügung beim Kriminalgericht des Kantons Luzern an. Das Gericht sprach ihn am 23. Oktober 2009 des gewerbsmässigen Betrugs, der mehrfachen Urkundenfälschung sowie des gewerbsmässigen betrügerischen Markengebrauchs schuldig. Es verurteilte ihn zu einer Freiheitsstrafe von acht Monaten sowie zu einer Geldstrafe von 90 Tagessätzen zu Fr. 180.--, je bedingt vollziehbar bei einer Probezeit von zwei Jahren.
Gegen dieses Urteil appellierte X._ beim Obergericht des Kantons Luzern. Dieses verurteilte ihn am 16. Dezember 2010 wegen gewerbsmässigen Betrugs, gewerbsmässiger Markenrechtsverletzung sowie gewerbsmässigen betrügerischen Markengebrauchs zu einer Geldstrafe von 330 Tagessätzen zu Fr. 180.--, bedingt vollziehbar bei einer Probezeit von zwei Jahren. Vom Vorwurf der mehrfachen Urkundenfälschung sprach es X._ frei.
C. X._ führt Beschwerde in Strafsachen beim Bundesgericht. Er beantragt, die Beschwerde sei gutzuheissen und Ziff. 1 (Schuldspruch), Ziff. 3 (Strafe) und Ziff. 5 (Kostenregelung) des Urteils des Obergerichts des Kantons Luzern vom 16. Dezember 2010 seien aufzuheben. Ausserdem sei er von Schuld und Strafe freizusprechen, eventuell sei die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen.
D. Das Obergericht des Kantons Luzern beantragt, die Beschwerde sei abzuweisen. Die Staatsanwaltschaft des Kantons Luzern stellt den Antrag, die Beschwerde sei unter Kostenfolge zulasten von X._ abzuweisen, soweit darauf einzutreten sei. Eventuell sei die Vorinstanz zur teilweisen Anpassung der Parteientschädigung für das Untersuchungsverfahren anzuweisen. Die Sortenorganisation beantragt, die Beschwerde sei unter Kosten- und Entschädigungsfolge zulasten von X._ abzuweisen.

Erwägungen:
1. 1.1 Der Beschwerdeführer rügt eine willkürliche Feststellung des Sachverhalts. Die Vorinstanz gehe davon aus, es bestehe ein Unterschied zwischen sortenechtem Appenzeller Käse und Appenzeller Schnittkäse. Die Annahme, nur der sortenechte Appenzeller Käse erfülle die Qualitätsvorgaben und durchlaufe sämtliche vorgeschriebenen Verfahrensabläufe, sei willkürlich. Es sei im Urteil nicht ersichtlich, aus welchen Untersuchungsergebnissen diese Feststellung abgeleitet werde. Die Produktions- und Kontrollabläufe seien von den Strafbehörden bei dem von ihm verkauften Schnittkäse nicht abgeklärt worden. Die Vorinstanz verletze den Untersuchungsgrundsatz, indem sie den sichergestellten Schnittkäse nie durch einen Experten untersucht habe. Es fänden sich in den Akten nicht einmal Hinweise, dass der Appenzeller Schnittkäse generell einer weniger strengen Qualitätskontrolle unterliege. Selbst wenn dies der Fall wäre, könne dem Beschwerdeführer kein strafbares Verhalten angelastet werden. Die Vorinstanz müsste im konkreten Fall die Nichtdurchführung der Qualitätskontrolle nachweisen. Sie verletze daher die Grundsätze der Unschuldsvermutung sowie "in dubio pro reo" (Beschwerde, S. 5 f.).
Der Beschwerdeführer erwähnt weiter, Appenzeller Käse werde in einem einheitlichen Produktionsgang hergestellt. Ob das Endprodukt als Appenzeller Käse oder als Appenzeller Schnittkäse auf den Markt komme, entscheide sich erst, wenn die vorgeschriebene Lagerung und Pflege bereits vollständig abgeschlossen seien. Während der Lagerung fänden alle vorgeschriebenen Kontrollen statt. Der Grund der späteren unterschiedlichen Einteilung erfolge nicht aufgrund der unterschiedlichen Qualität, sondern aufgrund der Mengensteuerpolitik der Sortenorganisation. Der Schnittkäse unterliege nicht der von der Sortenorganisation verordneten Absatzbeschränkung. Welches Produkt auf den Markt gelange, hänge mit anderen Worten lediglich davon ab, ob der Produzent bzw. Händler sein Kontingent für den sortenechten Appenzeller bereits aufgebraucht habe oder nicht. Er hätte daher seinen Käse als sortenechten Appenzeller beziehen können, wenn der Lieferant nicht sein Kontingent bereits ausgeschöpft hätte (Beschwerde, S. 7).
Es widerspreche der wirtschaftlichen Vernunft, den teureren Appenzeller zu kaufen, wenn die beiden Käsesorten dieselbe Qualität aufwiesen. Vor allem die zahlungskräftigen Konsumenten leiteten aufgrund des höheren Preises Exklusivität und bessere Qualität ab. Dies zeige sich nicht nur bei Luxusgütern, sondern auch bei Lebensmitteln wie zum Beispiel Mineralwasser. Es gehe nicht an, ihn wegen dieses unvernünftigen Kaufverhaltens verantwortlich zu machen (Beschwerde, S. 7 f.).
1.2 Die Vorinstanz erwägt, es sei nicht entscheidend, ob sich sortenechter Appenzeller Käse und Schnittkäse in Bezug auf die Zusammensetzung und Verarbeitung unterschieden. Der Unterschied bestehe bereits darin, dass die beiden Käsearten nicht dieselbe Qualitätskontrolle durchliefen. Die Sortenorganisation übe eine gesamtheitliche Kontrolle und Steuerung des sortenechten Appenzeller Käses von der Herstellung bis zum Vertrieb aus und habe ein entsprechendes Kontroll- und Vermarktungssystem aufgebaut, das eine gleichbleibende Qualität garantiere. Nur jener Käse werde einheitlich gekennzeichnet, trage die Marke Appenzeller und erhalte Exportprämien, der die Qualitätskriterien erfülle und die vorgeschriebenen Verfahren und Kontrollen durchlaufe. Indem die Kunden auf die Qualität und Kontrolle vertrauen könnten, seien sie bereit, einen höheren Preis zu bezahlen (angefochtenes Urteil, S. 10 f.).
1.3 Dem Sachgericht steht im Bereich der Beweiswürdigung ein erheblicher Ermessensspielraum zu (Urteil 6B_1090/2010 vom 14. Juli 2011 E. 1.5; <ref-ruling> E. 4d). Das Bundesgericht greift auf Beschwerde hin nur ein, wenn das Sachgericht diesen missbraucht, insbesondere offensichtlich unhaltbare Schlüsse zieht, erhebliche Beweise übersieht oder solche willkürlich ausser Acht lässt (<ref-ruling> E. 2.1; zum Begriff der Willkür <ref-ruling> E. 2.4 mit Hinweisen). Inwiefern das kantonale Gericht sein Ermessen im dargelegten Sinn missbraucht haben soll, ist in der Beschwerde klar und detailliert aufzuzeigen (<ref-ruling> E. 1.3). Auf ungenügend begründete Rügen und bloss allgemein gehaltene appellatorische Kritik am angefochtenen Entscheid tritt das Bundesgericht nicht ein (<ref-ruling> E. 2.2 mit Hinweis).
1.4 Der Beschwerdeführer zeigt nicht auf, und es ist auch nicht ersichtlich, inwiefern die Vorinstanz ihr Ermessen missbraucht hätte, indem sie den sortenechten Appenzeller Käse und den Schnittkäse als nicht identisch einstufte. Sie legt die Unterschiede ausführlich dar (angefochtenes Urteil, S. 10 f.) und weist ausserdem auf das von der Sortenorganisation erlassene Markenreglement hin (Doss. I Fasz. kl. Bel. I act. 7 der Vorakten). Ziff. 4 und 5 dieses Reglements regeln Herkunft und Qualität der unter der Marke Appenzeller verkauften Käse. Detaillierte Qualitätsanforderungen ergeben sich überdies aus dem Basisreglement der Sortenorganisation vom 23. Februar 1999 (Amtl. Bel. Obergericht act. 1 der Vorakten). Art. 19 dieses Reglements legt zum Beispiel ausführlich die Qualitätskriterien für die verschiedenen sortenechten Appenzeller Käse fest und teilt diese ausserdem in die Klassen Ia, IIa und IIIa ein. Gemäss Art. 20 lässt die Sortenorganisation die übernommenen Käse auf Fett- und Wassergehalt untersuchen, wobei die Proben "von jeder Tagesproduktion, jedem Kessi, jeder Wanne oder Charge" von der milchwirtschaftlichen Zentralstelle Flawil erhoben werden. Art. 21 regelt den Fettgehalt in der Trockenmasse des Käses, wobei der Käseproduzent die Abweichungen des idealen Fettgehalts bis ± 5 % finanziell abgelten muss. Ausserhalb dieser Toleranz wird der Käse von der Sortenorganisation bestmöglich (als nicht sortenechten Käse) verwertet. Art. 26 Abs. 3 schliesslich verlangt, dass Appenzeller Käse frühestens nach drei Monaten durch die Handelsfirmen freigegeben werden dürfen.
Die Schnittkäse unterstehen diesen Anforderungen nicht, weshalb die Vorinstanz, ohne in Willkür zu verfallen, annehmen durfte, dass der höhere Preis für den sortenechten Appenzeller Käse auf Qualitätsunterschiede zurückzuführen ist.
1.5 Nicht stichhaltig ist das Vorbringen des Beschwerdeführers, sein Anspruch auf rechtliches Gehör sei verletzt, weil die Vorinstanz nicht auf seinen Einwand eingegangen sei, den Deliktsbetrag nach dem Nettoprinzip zu berechnen und nicht auf den Bruttoerlös abzustellen (Beschwerde, S. 18). Er macht nicht geltend, die inkriminierten Handlungen seien aufgrund des von ihm berechneten tieferen Deliktsbetrags nicht gewerbsmässig gewesen. Dies ist auch nicht ersichtlich. Der Beschwerdeführer begründet zudem nicht, inwiefern die Vorinstanz die Strafzumessung nicht korrekt vorgenommen hätte oder die Strafe unzulässig hoch ausgefallen wäre. Er spricht an anderer Stelle vielmehr davon, die Vorinstanz habe bei der Strafsanktion "eine wesentliche reformatio in melius" durchgeführt (Beschwerde, S. 20).
1.6 Unbehelflich sind die Ausführungen des Beschwerdeführers, wonach die Vorinstanz die Nichtdurchführung der Qualitätskontrolle für den Schnittkäse im konkreten Fall nachweisen müsste. Entgegen seiner Auffassung kann mit Blick auf das Markenreglement der Sortenorganisation nicht auf einen einheitlichen Produktionsgang des sortenechten Käses sowie des Schnittkäses geschlossen werden, worauf die Vorinstanz denn auch hinweist. Entsprechend entscheidet sich nicht zwingend erst nach Abschluss der vorgeschriebenen Lagerung und Pflege sowie aufgrund der Mengensteuerpolitik der Sortenorganisation, ob das Endprodukt als Appenzeller Käse oder als Schnittkäse auf den Markt kommt. Vielmehr ist es möglich und sogar wahrscheinlich, dass diejenigen Käse, welche die vorgegebenen Qualitätskriterien nicht erfüllen, als Schnittkäse verwertet werden, worauf Art. 21 des Markenreglements hindeutet, der diesfalls eine "bestmögliche Verwertung" vorschreibt.
1.7 Ebenso wenig verletzt die Verurteilung wegen Betrugs den Grundsatz "nulla poena sine lege". Die Vorinstanz widerlegt mit ihren Sachverhaltsfeststellungen seine Begründung, wonach er nichts anderes getan habe, als sortenechten Appenzeller Käse zu einem besonders günstigen Preis einzukaufen, um diesen dann zum marktüblichen Preis weiter zu verkaufen (Beschwerde, S. 17 f.).
1.8 Der Beschwerdeführer behauptet, die Vorinstanz stelle auf den angeblichen Verkauf von Käse ab, der nicht die gleichen Qualitätskontrollen durchlaufen habe wie der sortenechte Appenzeller Käse. Dieses Unterscheidungsmerkmal sei nicht Gegenstand der Untersuchung gewesen (Beschwerde, S. 18). In der Anklageschrift wird dem Beschwerdeführer hinreichend deutlich vorgeworfen, er habe die Kunden über die Qualität, die Echtheit sowie den markengerechten Preis des ihnen verkauften Produkts getäuscht. Zudem sei ihm bewusst gewesen, dass der Schnittkäse nicht nach den Vorgaben der Sortenorganisation hergestellt und erfasst worden war (Anklageschrift, S. 12). Die vom Beschwerdeführer monierte Verletzung des Anklagegrundsatzes liegt somit nicht vor.
1.9 Ohne Relevanz sind schliesslich die Argumente des Beschwerdeführers im Zusammenhang mit dem Lizenzvertrag vom 6. September 2000 zwischen der B._ AG und der Sortenorganisation (Doss. I Fasz. kl. Bel. I act. 28 der Vorakten). Er habe gestützt auf diesen Vertrag nicht annehmen müssen, dass eine Mengenbeschränkung bestehe und habe sich auch nicht an die Mengensteuerpolitik halten müssen. Der Vertrag enthalte zwar ausdrücklich eine Bestimmung über die Qualität, nicht jedoch über die zulässige Menge des Einkaufs oder Weiterverkaufs. Als Nichtgesellschafterin der Sortenorganisation komme der B._ AG die Stellung "Drittunternehmen" zu, das lediglich den Verpflichtungen des Lizenzvertrags unterliegt. Es sei ihr daher nicht untersagt gewesen, die Marke "Appenzeller Käse" beim Schnittkäse zu verwenden. Vielmehr sei sie dazu nach Ziff. 4 des Lizenzvertrags verpflichtet gewesen (Beschwerde, S. 9 ff.). Die Vorinstanz weist ausführlich nach, inwiefern der Beschwerdeführer um die Bedeutung des Markenschutzes sowie der korrekten Bezeichnung der Käse für die Sortenorganisation und die Beteiligten wusste oder zumindest hätte wissen müssen. Seine gegenteiligen Äusserungen stellten Schutzbehauptungen dar. Auf die vorinstanzlichen Ausführungen (angefochtenes Urteil, S. 10 ff.) kann gestützt auf <ref-law> verwiesen werden.
2. 2.1 Der Beschwerdeführer rügt verschiedene Fehler bei der Rechtsanwendung, weshalb eine Verurteilung wegen Betrugs nicht in Frage komme. Er habe seinen Kunden stets den bestellten sortenechten Appenzeller Käse verkauft, weshalb nie eine Täuschung stattgefunden habe. Die Käufer hätten auch keinen Schaden erlitten. Ebenso wenig habe eine Täuschung in Bezug auf die Exportprämien gegenüber der Beschwerdegegnerin 2 stattgefunden. Voraussetzung dieser Prämie sei einzig der Vertrieb von Appenzeller Käse ins Ausland gewesen. Es liege kein Beweis vor, wonach dieser Anspruch auf kontingentierten Käse beschränkt gewesen sei. Dass seine Lieferantin keine Abgabe an die Sortenorganisation bezahlt habe, könne ihm nicht zum Nachteil gereichen. Er habe sich um deren Pflichten nicht kümmern müssen. Es wäre Sache der Beschwerdegegnerin 2 gewesen zu prüfen, ob die Abgabe für den von ihm exportierten Käse bezahlt und damit der Anspruch auf eine Exportprämie berechtigt gewesen sei. Die Vorinstanz verletze ihre Begründungspflicht, indem sie lediglich festhalte, eine Überprüfung sei für die Beschwerdegegnerin 2 nicht möglich oder zumutbar gewesen. Aufgrund der Opfermitverantwortung sei ein Betrug zu verneinen (Beschwerde, S. 16 f.).
Weiter habe er nicht gegen das Markenschutzgesetz verstossen, da er ausschliesslich Markenware in Verkehr gesetzt habe, wozu er als lizenzierter Käsehändler berechtigt gewesen sei. Es sei offensichtlich, dass er die Marke Appenzeller nicht unrechtmässig verwendet habe. In rechtlicher Hinsicht werde überdies der betrügerische Markengebrauch durch den Betrugstatbestand konsumiert (Beschwerde, S. 16).
2.2 Die Vorinstanz erwägt, der Beschwerdeführer habe den Käufern Schnittkäse als sortenechten Appenzeller Käse verkauft, wobei es für diese weder möglich noch zumutbar gewesen sei, dies zu überprüfen. Die Unterschiede zwischen den beiden Käsearten seien dem Beschwerdeführer bekannt gewesen bzw. hätten ihm bekannt sein müssen. Die Käufer seien davon ausgegangen, es handle sich um sortenechten Appenzeller Käse, der die von der Sortenorganisation vorgeschriebenen Verfahrensabläufe und Kontrollen durchlaufen habe. Sie seien deshalb bereit gewesen, hierfür einen höheren Preis zu bezahlen, wodurch sie sich am Vermögen geschädigt und dem Beschwerdeführer einen Vermögensvorteil verschafft hätten (angefochtenes Urteil, S. 14).
Die Vorinstanz führt weiter aus, der Beschwerdeführer habe die Beschwerdegegnerin 2 über die Menge des tatsächlich ausgeführten sortenechten Appenzeller Käses getäuscht. Eine Überprüfung sei für diese weder möglich noch zumutbar gewesen. Sie sei daher von einer zu hohen Menge an exportiertem sortenechten Appenzeller Käse ausgegangen, habe die Exportprämien ausgerichtet und sich selbst am Vermögen geschädigt (angefochtenes Urteil, S. 14 f.).
Die Vorinstanz stuft die deliktische Tätigkeit des Beschwerdeführers als gewerbsmässig ein, weil er während acht Monaten mehrfach Schnittkäse als sortenechten Appenzeller Käse verkauft und unberechtigterweise Exportprämien bezogen habe. Er habe über einen längeren Zeitraum einen erheblichen Aufwand betrieben und beträchtliche Einkünfte erwirtschaftet. Er habe damit seine Tätigkeit nach Art eines Berufes ausgeübt und so Mehrerträge im Umfang von rund Fr. 150'000.-- erzielt (angefochtenes Urteil, S. 15).
Die Vorinstanz bejaht auch eine gewerbsmässige Markenrechtsverletzung nach Art. 61 des Bundesgesetzes vom 28. August 1992 über den Schutz von Marken und Herkunftsangaben (Markenschutzgesetz, MSchG; SR 232.11). Der Beschwerdeführer habe durch das Anbringen der Laibetiketten für sortenechten Appenzeller Käse auf Schnittkäse die Marke der Beschwerdegegnerin 2 gewerbsmässig benutzt und damit tatbestandsmässig gehandelt. Vom ebenfalls erfüllten Tatbestand der Urkundenfälschung spricht sie ihn frei, da die widerrechtliche Kennzeichnung mit einer fremden Marke nur als Markenverletzung zu bestrafen sei (angefochtenes Urteil, S. 17 ff.).
Ebenso habe er sich durch das widerrechtliche Kennzeichnen von Schnittkäse mit der Marke der Beschwerdegegnerin 2 des gewerbsmässigen betrügerischen Markengebrauchs nach <ref-law> schuldig gemacht. Er habe den Anschein erweckt, es handle sich um sortenechten Appenzeller Käse, womit er den Tatbestand mehrfach erfüllt und auch gewerbsmässig gehandelt habe (angefochtenes Urteil, S. 19 ff.).
2.3 Gemäss <ref-law> macht sich des Betrugs u.a. schuldig, wer in der Absicht, sich oder einen andern unrechtmässig zu bereichern, jemanden durch Vorspiegelung oder Unterdrückung von Tatsachen arglistig irreführt und so den Irrenden zu einem Verhalten bestimmt, wodurch dieser sich selbst oder einen andern am Vermögen schädigt. Handelt der Täter gewerbsmässig, so wird er nach <ref-law> mit Freiheitsstrafe bis zu zehn Jahren oder Geldstrafe nicht unter 90 Tagessätzen bestraft.
Auf Antrag des Verletzten wird gemäss <ref-law> mit Freiheitsstrafe bis zu einem Jahr oder Geldstrafe bestraft, wer vorsätzlich das Markenrecht eines anderen verletzt, indem er sich die Marke des anderen anmasst oder diese nachmacht oder nachahmt (lit. a); unter der angemassten, nachgemachten oder nachgeahmten Marke Waren in Verkehr setzt oder Dienstleistungen erbringt, solche Waren oder Dienstleistungen anbietet, ein-, aus- oder durchführt oder für sie wirbt (lit. b). Handelt der Täter gewerbsmässig, so wird er von Amtes wegen verfolgt. Die Strafe ist Freiheitsstrafe bis zu fünf Jahren oder Geldstrafe. Mit der Freiheitsstrafe ist eine Geldstrafe zu verbinden (Abs. 3).
Nach <ref-law> wird auf Antrag des Verletzten mit Freiheitsstrafe bis zu einem Jahr oder Geldstrafe bestraft, wer Waren oder Dienstleistungen zum Zwecke der Täuschung widerrechtlich mit der Marke eines anderen kennzeichnet und auf diese Weise den Anschein erweckt, es handle sich um Originalwaren oder -dienstleistungen (lit. a); widerrechtlich mit der Marke eines anderen gekennzeichnete Waren oder Dienstleistungen als Originalwaren anbietet oder in Verkehr setzt oder als Originaldienstleistungen anbietet oder erbringt (lit. b).
Handelt der Täter gewerbsmässig, so wird er von Amtes wegen verfolgt. Die Strafe ist Freiheitsstrafe bis zu fünf Jahren oder Geldstrafe. Mit der Freiheitsstrafe ist eine Geldstrafe zu verbinden (Abs. 2).
2.4 Die vom Beschwerdeführer angeführten Gründe, weshalb ihn die Vorinstanz zu Unrecht wegen Betrugs verurteilt habe, sind unbehelflich. Die Vorinstanz weist überzeugend nach, dass er seinen Kunden im In- und Ausland Schnittkäse als (teureren) sortenechten Appenzeller Käse verkauft hat. Die Kunden sind hierüber durch den Beschwerdeführer getäuscht worden und haben einen finanziellen Schaden erlitten. Auf die vorinstanzlichen Ausführungen kann verwiesen werden (<ref-law>). Die Ausrichtung von Exportprämien durch die Sortenorganisation ist an die Ausfuhr von sortenechtem Appenzeller Käse gebunden, was dem Beschwerdeführer bekannt war (Einvernahme des Amtsstatthalters Sursee, Fasz. Rogatorien 1, S. 13, Frage 81 der Vorakten). Dass gemäss Vorinstanz eine systematische Überprüfung sämtlicher Ausfuhren durch die Sortenorganisation unmöglich bzw. unzumutbar ist, erscheint einleuchtend. Eine Opfermitverantwortung ist daher zu verneinen.
Die Ausführungen des Beschwerdeführers im Zusammenhang mit den nicht bezahlten Abgaben an die Sortenorganisation durch die Lieferantin des Schnittkäses können hieran nichts ändern, zumal erst er den Schnittkäse als sortenechten Appenzeller Käse weiterverkaufte. Die Lieferantin war daher nicht gehalten, Abgaben an die Sortenorganisation zu entrichten. Die Vorinstanz hat zu Recht den Tatbestand des Betrugs bejaht.
2.5 Unzutreffend erweisen sich auch die Vorbringen des Beschwerdeführers in Bezug auf die Anwendung der Markenschutzgesetzgebung, zumal die Vorinstanz nachweist, dass er Markenware auf unerlaubte Weise in Verkehr gesetzt hat. Die vorinstanzlichen Ausführungen zur Anwendung der Art. 61 und Art. 62 MSchG erweisen sich als korrekt, worauf verwiesen werden kann (<ref-law>).
2.6 Ob im Verhältnis des betrügerischen Markengebrauchs zum Betrug von einem Vorrang des Betrugstatbestandes oder echter Konkurrenz auszugehen ist, wird in der Lehre unterschiedlich beurteilt. Während RÜETSCHI von einem Vorrang des Betrugstatbestandes aufgrund der höheren Strafdrohung ausgeht (DAVID RÜETSCHI, in: Michael Noth/Gregor Bühler/Florent Thouven [Hrsg.], Stämpflis Handkommentar zum Markenschutzgesetz [MSchG], Bern 2009, Art. 62 N 21), besteht nach anderen Autoren echte Konkurrenz zwischen den beiden Tatbeständen (CORSIN BLUMENTHAL, Der strafrechtliche Schutz der Marke, Diss. Freiburg, Bern 2002, S. 347 ff.; CHRISTOPH WILLI, Markenschutzgesetz Kommentar, Zürich 2002, Art. 62 N 7, zumindest, wenn der Betrug über die widerrechtliche Kennzeichnung hinausgeht). Von echter Konkurrenz geht auch die Vorinstanz aus (angefochtenes Urteil, S. 20 f.).
Während beim strafrechtlichen Betrug das Vermögen sowie Treu und Glauben im Geschäftsverkehr die geschützten Rechtsgüter darstellen, schützt der betrügerische Markengebrauch neben Treu und Glauben im Geschäftsverkehr nicht das Vermögen des Abnehmers der entsprechenden Ware, sondern das ausschliessliche Recht des Markeninhabers an seiner Marke. Die Schutzobjekte der beiden Tatbestände erweisen sich daher als verschieden, weshalb diese richtigerweise in echter Konkurrenz anzuwenden sind (BLUMENTHAL, a.a.O., S. 347 f.).
Der Beschwerdeführer kennzeichnete nicht nur den Schnittkäse als sortenechten Appenzeller Käse, sondern traf zusätzliche Machenschaften, die neben den Kunden auch die Sortenorganisation am Vermögen schädigte. Die Vorinstanz verletzt mit der Verurteilung des Beschwerdeführers wegen Betrugs, Markenrechtsverletzung und betrügerischen Markengebrauchs somit kein Bundesrecht.
3. 3.1 Der Beschwerdeführer bringt weiter vor, die Vorinstanz habe die Kostenauflage unrichtig vorgenommen und damit <ref-law> sowie <ref-law> verletzt. Es gehe nicht an, ihm die vollen Parteikosten im Untersuchungsverfahren von Fr. 8'056.-- zu überbinden, obwohl sich gemäss den Ausführungen des Amtsstatthalteramts Sursee mindestens ein Drittel der klägerischen Aufwendungen auf das Verfahren in Sachen A._ bezogen hätten und diesem entsprechend ein Drittel dieser Kosten überbunden worden seien. Er habe lediglich noch zwei Drittel der Parteikosten, d.h. Fr. 5'370.--, zu übernehmen.
Zudem habe er keine Entschädigung erhalten, obwohl im Laufe des Verfahrens einzelne Anklagepunkte fallen gelassen bzw. gerichtliche Teilfreisprüche erfolgt seien. So sei er bereits vom Kriminalgericht vom Vorwurf der Urkundenfälschung freigesprochen worden, und eine Verurteilung wegen Warenfälschung sei nicht erfolgt. Die Vorinstanz habe ihn bezüglich Urkundenfälschung vollständig freigesprochen, zudem habe es keine Verurteilung wegen Urkundenunterdrückung gegeben. Da diese Delikte als Verbrechen gälten, habe er sich intensiv und mit entsprechendem Aufwand verteidigen müssen. Die Vorinstanz habe eine wesentlich mildere Sanktion als das Kriminalgericht ausgesprochen. Auch dies habe nicht unwesentliche Aufwendungen der Verteidigung bedingt (Beschwerde, S. 19 f.).
3.2 In Bezug auf die Frage des anwendbaren Prozessrechts ist die bis zum 31. Dezember 2010 in Kraft stehende Strafprozessordnung des Kantons Luzern anwendbar (Art. 453 Abs. 1 der schweizerischen Strafprozessordnung vom 5. Oktober 2007 [StPO, SR 312.0]). Deren Anwendung überprüft das Bundesgericht nur unter dem Gesichtspunkt einer Verletzung des Willkürverbots gemäss <ref-law> (Urteil 6B_143/2010 vom 22. Juni 2010 E. 2.1 mit Hinweis auf BGE 116 la 162 E. 2f). Ausserdem prüft das Bundesgericht gemäss <ref-law> die Verletzung von kantonalem Recht nur insofern, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist.
Der Beschwerdeführer beruft sich lediglich auf die Schweizerische Strafprozessordnung. Er bringt jedoch nicht vor, welche kantonale Norm durch die Kostenauflage der Vorinstanz willkürlich angewendet worden sein soll. Auf seine Rügen im Zusammenhang mit der Kostenauflage und Entschädigung ist daher nicht einzutreten.
3.3 Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Verfahrensausgang sind die bundesgerichtlichen Kosten dem Beschwerdeführer aufzuerlegen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 4'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Luzern, II. Kammer, schriftlich mitgeteilt.
Lausanne, 24. Februar 2012
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Der Gerichtsschreiber: Keller