Sachverhalt:
A. X._ erstattete am 26. August 2010 Strafanzeige gegen seine von ihm getrennt lebende Ehefrau Y._ wegen falscher Anschuldigung im Sinne von <ref-law>. Gleichzeitig machte er Zivilforderungen geltend. Mit Entscheid vom 18. Oktober 2010 stellte das damals für die Untersuchung zuständige Amtsstatthalteramt Luzern das Strafverfahren gegen Y._ ein und trat auf die Zivilforderungen von X._ nicht ein. Der Staatsanwalt visierte den Einstellungsentscheid am 26. Oktober 2010.
Gegen den Einstellungsentscheid reichte X._ am 15. November 2010 Rekurs ein. Er beantragte die Überweisung der Strafsache an das zuständige Gericht und ersuchte zudem um Gewährung unentgeltlicher Rechtspflege. Mit Entscheid vom 25. März 2011 trat das Obergericht des Kantons Luzern auf den Rekurs nicht ein. Zur Begründung führte es an, weder habe sich X._ als Privatkläger im Sinne von § 35 Abs. 1 des Gesetzes des Kantons Luzern vom 3. Juni 1957 über die Strafprozessordnung (SRL 305; im Folgenden: StPO/LU) konstituiert, noch komme ihm Opferstellung nach dem Opferhilfegesetz (SR 312.5) zu. Das Gesuch um unentgeltliche Rechtspflege wies das Obergericht wegen Aussichtslosigkeit ab.
B. Mit Beschwerde in Strafsachen an das Bundesgericht vom 18. Mai 2011 beantragt X._ im Wesentlichen die Aufhebung des Entscheids des Obergerichts.
Das Obergericht beantragt in seiner Vernehmlassung die Abweisung der Beschwerde. Die Oberstaatsanwaltschaft und die Beschwerdegegnerin haben auf eine Stellungnahme verzichtet.

Erwägungen:
1. 1.1 Der angefochtene Entscheid betrifft die Einstellung einer Strafuntersuchung. Dagegen ist die Beschwerde in Strafsachen nach <ref-law> gegeben.
1.2 Die Einstellungsverfügung datiert vom 18. Oktober 2010. Anwendbar ist deshalb die luzernische Strafprozessordnung und nicht die am 1. Januar 2011 in Kraft getretene Schweizerische Strafprozessordnung (StPO, SR 312.0; siehe Art. 453 f. StPO und Urteil 1B_411/2010 vom 7. Februar 2011 E. 1.3 mit Hinweisen).
1.2 Die Einstellungsverfügung datiert vom 18. Oktober 2010. Anwendbar ist deshalb die luzernische Strafprozessordnung und nicht die am 1. Januar 2011 in Kraft getretene Schweizerische Strafprozessordnung (StPO, SR 312.0; siehe Art. 453 f. StPO und Urteil 1B_411/2010 vom 7. Februar 2011 E. 1.3 mit Hinweisen).
1.3 1.3.1 Zur Beschwerde in Strafsachen ist nach <ref-law> berechtigt, wer vor der Vorinstanz am Verfahren teilgenommen hat oder keine Möglichkeit zur Teilnahme erhalten hat (lit. a) und ein rechtlich geschütztes Interesse an der Aufhebung oder Änderung des angefochtenen Entscheids hat (lit. b). Da der angefochtene Entscheid nach dem 31. Dezember 2010 datiert, beurteilt sich die Frage des rechtlich geschützten Interesses nach der am 1. Januar 2011 in Kraft getretenen Fassung von <ref-law> (<ref-law>). Danach wird der Privatklägerschaft ein rechtlich geschütztes Interesse zuerkannt, wenn der angefochtene Entscheid sich auf die Beurteilung ihrer Zivilansprüche auswirken kann (Art. 81 Abs. 1 lit. b Ziff. 5 BGG). In der bis zum 1. Januar 2011 geltenden Fassung dieser Bestimmung wurde dagegen nicht die Privatklägerschaft schlechthin, sondern nur das Opfer als beschwerdelegitimiert bezeichnet; dies ebenfalls unter der Voraussetzung, dass sich der angefochtene Entscheid auf die Beurteilung seiner Zivilansprüche auswirken kann.
Nach der Praxis zur Beschwerdebefugnis des Opfers (aArt. 81 Abs. 1 lit. b Ziff. 5 BGG; vgl. auch Urteil 6B_127/2007 vom 23. Juli 2007 E. 2) konnte dieses gegen ein Strafurteil, durch das der Angeschuldigte freigesprochen wurde, Rechtsmittel im Strafpunkt grundsätzlich nur erheben, wenn es, soweit zumutbar, seine Zivilansprüche aus strafbarer Handlung im Strafverfahren geltend gemacht hatte. Dies wurde damit begründet, dass das Strafverfahren nicht blosses Vehikel zur Durchsetzung von Zivilforderungen in einem Zivilprozess sein soll, den das Opfer erst nach Abschluss des Strafprozesses, je nach dessen Ausgang, anzustrengen gedenkt. Vielmehr sollte das Opfer, soweit zumutbar, seine Zivilansprüche im Strafverfahren geltend machen (<ref-ruling> E. 1.2.2 S. 198; <ref-ruling> E. 1 S. 186 ff.; <ref-ruling> E. 4b S. 54 f.; Urteil 6B_260/2009 vom 30. Juni 2009 E. 2.2.1 mit Hinweisen; vgl. auch <ref-ruling> E. 3 S. 164 mit Hinweisen). Anders verhielt es sich im Falle der Einstellung des Strafverfahrens. Da diesfalls vom Opfer nicht verlangt werden kann, dass es bereits adhäsionsweise Zivilforderungen geltend gemacht hat, reichte es, wenn es im Verfahren vor Bundesgericht darlegte, aus welchen Gründen sich der angefochtene Entscheid inwiefern auf welche Zivilforderungen auswirken kann (<ref-ruling> E. 1.2.2 S. 199; <ref-ruling> E. 1 S. 141; je mit Hinweisen).
Mit der Revision von Art. 81 Abs. 1 lit. b Ziff. 5 BGG wurde die Legitimation auf die Privatklägerschaft erweitert. Die zusätzliche Voraussetzung, dass sich der angefochtene Entscheid auf die Beurteilung der Zivilansprüche auswirken kann, blieb jedoch unverändert. An der Praxis, dass der Beschwerdeführer, soweit zumutbar, seine Zivilansprüche im Strafverfahren geltend gemacht haben muss, ist deshalb ebenso festzuhalten wie an der Ausnahme im Falle von Verfahrenseinstellungen.
1.3.2 Streitgegenstand ist vorliegend, ob das Obergericht des Kantons Luzern zu Recht auf den bei ihm erhobenen Rekurs nicht eingetreten ist (vgl. <ref-ruling> E. 1.2 S. 41). Der Beschwerdeführer beanstandet, die Vorinstanz sei in überspitzten Formalismus verfallen, indem sie seine Eigenschaft als Privatkläger verneint habe. Zudem sei sie zu Unrecht von fehlender Opfereigenschaft nach dem Opferhilfegesetz ausgegangen. Damit rügt der Beschwerdeführer die Verletzung von Rechten, die ihm als am Verfahren beteiligte Partei nach dem massgebenden Prozessrecht oder unmittelbar aufgrund der BV oder der EMRK zustehen. Dazu ist er legitimiert (<ref-law>; <ref-ruling> E. 1.9 S. 40; <ref-ruling> E. 1.3.2 S. 253; <ref-ruling> E. 6.2 S. 198 ff.; je mit Hinweisen).
1.4 Die weiteren Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass. Auf die Beschwerde ist einzutreten.
2. 2.1 Der Beschwerdeführer bringt vor, er habe die Strafanzeige vom 26. August 2010 ohne anwaltliche Vertretung verfasst. Dabei habe er sich weder als Anzeigeerstatter noch als Privatkläger bezeichnet. Indessen habe er verlangt, dass das Strafverfahren an die Hand genommen werde, zudem habe er Zivilansprüche geltend gemacht. In der Folge seien keine Untersuchungen durchgeführt worden. Vielmehr hätten die Untersuchungsbehörden das Verfahren aufgrund der Akten eingestellt. Ihm selbst sei keine Gelegenheit gegeben worden, sich auch noch formell als Privatkläger zu konstituieren, obwohl nach <ref-law>/LU der Geschädigte in allen Fällen im Untersuchungsverfahren auf das Recht der Privatklage und auf deren Folgen aufmerksam zu machen sei. Die Staatsanwaltschaft habe das Nichteintreten auf die Zivilansprüche zudem nicht damit begründet, dass er sich nicht als Privatkläger konstituiert habe. Dass das Obergericht darauf abstelle, ob er den Begriff des Privatklägers ausdrücklich nenne, stelle unter diesen Voraussetzungen überspitzten Formalismus (<ref-law>) dar.
2.2 Überspitzter Formalismus als besondere Form der Rechtsverweigerung ist gegeben, wenn für ein Verfahren rigorose Formvorschriften aufgestellt werden, ohne dass die Strenge sachlich gerechtfertigt wäre, wenn die Behörde formelle Vorschriften mit übertriebener Schärfe handhabt oder an Rechtsschriften überspannte Anforderungen stellt und damit dem Bürger den Rechtsweg in unzulässiger Weise versperrt (<ref-ruling> E. 2.1 S. 9 mit Hinweisen).
2.3 Im angefochtenen Entscheid wird ausgeführt, es sei aus den Akten nicht ersichtlich und es werde auch nicht behauptet, dass sich der Beschwerdeführer als Privatkläger im Strafverfahren konstituiert habe. Dies wäre aber notwendige Voraussetzung, um im Rechtsmittelverfahren aktivlegitimiert zu sein bzw. entsprechende Parteirechte im Strafverfahren ausüben zu können. Der Beschwerdeführer sei bloss Antragsteller, der als vermeintlich Geschädigter zudem adhäsionsweise Zivilforderungen geltend mache.
2.4 Als Parteien gelten nach luzernischem Strafprozessrecht grundsätzlich der Angeschuldigte, die Staatsanwaltschaft sowie der Privatkläger (§ 32 Abs. 1 und 2 StPO/LU). Privatkläger ist, wer die Strafverfolgung des Täters verlangt (<ref-law>/LU). Zur Privatklage legitimiert ist der strafantragsberechtigte Geschädigte sowie derjenige, der durch die strafbare Handlung in seinen Interessen unmittelbar verletzt worden ist (<ref-law>/LU). Die Privatklage kann mündlich oder schriftlich beim Amtsstatthalteramt oder beim urteilenden Gericht eingereicht werden (<ref-law>/LU). Der Geschädigte ist in allen Fällen im Untersuchungsverfahren auf das Recht der Privatklage sowie auf deren Folgen aufmerksam zu machen (<ref-law>/LU). Mit der Privatklage können auch Zivilansprüche verbunden werden (<ref-law>/LU). Wird die Untersuchung eingestellt, so kann der Privatkläger Rekurs einlegen (<ref-law>/LU). Wird das Verfahren gegen den Angeschuldigten eingestellt (oder wird er freigesprochen), so können die Kosten ganz oder teilweise dem Privatkläger auferlegt werden. Auf Antrag kann der Privatkläger zudem zu einer angemessenen Entschädigung und Genugtuungssumme an den Angeschuldigten verurteilt werden (<ref-law>/LU; vgl. zum Ganzen auch Urteil 1P.255/1998 vom 13. Juli 1998).
2.5 Es trifft zu, wie aus den Erwägungen des Obergerichts hervorgeht, dass die adhäsionsweise Geltendmachung von Zivilforderungen nicht mit der Privatklage gleichgestellt werden kann (vgl. <ref-law>/LU). Aus der Strafanzeige vom 26. August 2010 geht lediglich hervor, dass der Beschwerdeführer das Amtsstatthalteramt ersuchte, das Verfahren umgehend an die Hand zu nehmen und ihm zulasten der Beschwerdegegnerin eine Genugtuung und eine Entschädigung zuzusprechen. Angesichts der Tatsache, dass er weder ausdrücklich Privatklage erhob noch darauf verzichtete, musste er indessen gemäss <ref-law>/LU auf dieses Recht und die Folgen der Privatklage aufmerksam gemacht werden. Der Beschwerdeführer bringt vor, dies sei nicht geschehen. Im Verfahren vor Bundesgericht wird dieser Darstellung von keiner Seite widersprochen. Den Akten lässt sich ebenfalls kein Hinweis darauf entnehmen, dass der Beschwerdeführer auf das Recht der Privatklage aufmerksam gemacht worden wäre. Vielmehr gibt es Hinweise darauf, dass die Staatsanwaltschaft bzw. das Amtsstatthalteramt sogar davon ausgingen, dem Beschwerdeführer komme die Stellung eines Privatklägers zu. So beantragte die Staatsanwaltschaft im vorinstanzlichen Verfahren in ihrer Vernehmlassung vom 15. Februar 2011, die Beschwerde sei abzuweisen, und nicht, es sei darauf nicht einzutreten. Weiter fällt auf, dass das Amtsstatthalteramt im Entscheid vom 14. Dezember 2009 betreffend die Einstellung der Strafuntersuchung gegen den Beschwerdeführer wegen sexueller Nötigung (welche im Zusammenhang mit dessen Anzeige wegen falscher Anschuldigung steht) erwägt, dass sich die Beschwerdegegnerin nicht als Privatklägerin konstituiert habe. Ein derartiger Hinweis fehlt im Einstellungsentscheid vom 18. Oktober 2010.
Vor diesem Hintergrund erscheint es als überspitzt formalistisch, dass die Vorinstanz einzig darauf abstellte, ob sich der Beschwerdeführer förmlich bzw. ausdrücklich als Privatkläger konstituierte. Der angefochtene Entscheid verletzt <ref-law> und ist deshalb aufzuheben.
3. Die Beschwerde ist gutzuheissen, der angefochtene Entscheid aufzuheben und die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen. Es erübrigt sich damit, auf die zweite, das Opferhilfegesetz betreffende Rüge des Beschwerdeführers einzugehen.
Bei diesem Ausgang des Verfahrens hätte grundsätzlich die Beschwerdegegnerin als unterliegende Partei die Kosten des bundesgerichtlichen Verfahrens zu tragen (<ref-law>) und dem anwaltlich vertretenen Beschwerdeführer eine Parteientschädigung zu entrichten (<ref-law>). Unnötige Kosten hat indessen zu bezahlen, wer sie verursacht (Art. 66 Abs. 3 und Art. 68 Abs. 4 BGG). Vorliegend hat das Obergericht des Kantons Luzern einen überspitzt formalistischen Entscheid gefällt und damit in qualifizierter Weise seine Pflicht zur Justizgewährleistung missachtet (Urteil 9C_251/2009 vom 15. Mai 2009 E. 2.1 mit Hinweisen). Es ist deshalb gerechtfertigt, den Kanton Luzern zu verpflichten, dem Beschwerdeführer für das bundesgerichtliche Verfahren eine angemessene Entschädigung auszurichten. Auf die Erhebung von Gerichtskosten wird verzichtet (vgl. zum Ganzen: <ref-ruling> E. 3 S. 248; Urteil 8C_984/2009 vom 21. Mai 2010 E. 5; je mit Hinweisen). Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege wird damit gegenstandslos.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, das Urteil des Obergerichts des Kantons Luzern vom 25. März 2011 aufgehoben und die Sache zur neuen Beurteilung an die Vorinstanz zurückgewiesen.
2. Es werden keine Gerichtskosten erhoben.
3. Der Kanton Luzern hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 1'500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, der Oberstaatsanwaltschaft und dem Obergericht des Kantons Luzern, 2. Abteilung, schriftlich mitgeteilt.
Lausanne, 15. Juli 2011
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Dold