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. 