Sachverhalt:
A. Die X._ AG (Beschwerdegegnerin) als Vermieterin und A._ (Beschwerdeführerin 1) als Mieterin schlossen in den Jahren 2005 und 2006 mehrere Mietverträge über eine 5.5-Zimmer-Wohnung, einen Disponibelraum und zwei Parkplätze. Mit Vereinbarung vom 31. August 2006 erklärte sich B._ (Beschwerdeführer 2) einverstanden, für alle Verbindlichkeiten aus dem Mietverhältnis betreffend die 5.5-Zimmer-Wohnung solidarisch mit der Beschwerdeführerin 1 zu haften. Am 25. März 2011 kündigte die Beschwerdegegnerin wegen Mietzinsausständen sämtliche Mietverhältnisse auf den 30. April 2011.
B. B.a Mit Gesuch vom 3. Mai 2011 an den Einzelrichter des Bezirksgerichts Hochdorf ersuchte die Beschwerdegegnerin um Ausweisung der Beschwerdeführer aus den Mieträumlichkeiten.
Mit Entscheid vom 14. Juni 2011 wies der Einzelrichter des Bezirksgerichts Hochdorf in Gutheissung des Gesuchs die Beschwerdeführer aus den Mieträumlichkeiten aus.
B.b Gegen diesen Entscheid erhoben die Beschwerdeführer am 27. Juni 2011 Berufung beim Obergericht des Kantons Luzern und beantragten, es sei der erstinstanzliche Entscheid aufzuheben und es sei das Gesuch der Beschwerdegegnerin abzuweisen, soweit darauf einzutreten sei. Eventualiter sei die Sache an das Bezirksgericht Hochdorf zurückzuweisen.
Mit Entscheid vom 17. August 2011 wies das Obergericht des Kantons Luzern die Berufung ab und wies die Beschwerdeführer unter Androhung der polizeilichen Vollstreckung an, innert 10 Tagen ab Zustellung des Entscheids sämtliche Mieträumlichkeiten ordnungsgemäss zu räumen, zu reinigen und unter Rückgabe des Schlüssels an die Beschwerdegegnerin zu verlassen.
C. Mit Beschwerde in Zivilsachen vom 2. September 2011 beantragen die Beschwerdeführer dem Bundesgericht, es sei der Entscheid des Obergerichts aufzuheben und das Gesuch um Ausweisung abzuweisen, soweit darauf einzutreten ist. Eventualiter sei die Sache zur Neubeurteilung an das Obergericht zurückzuweisen. Die Beschwerdeführer beantragen zudem die Erteilung der aufschiebenden Wirkung.
Die Beschwerdegegnerin beantragt die Abweisung des Gesuchs um aufschiebende Wirkung und die Abweisung der Beschwerde. Die Vorinstanz hat auf eine Vernehmlassung verzichtet.
D. Mit Präsidialverfügung vom 26. September 2011 wurde der Beschwerde die aufschiebende Wirkung erteilt.

Erwägungen:
1. Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (<ref-ruling> E. 1 S. 103, 470 E. 1 S. 472; <ref-ruling> E. 1).
1.1 Die Beschwerde richtet sich gegen einen verfahrensabschliessenden Entscheid (<ref-law>) einer oberen kantonalen Instanz, die auf ein Rechtsmittel hin kantonal letztinstanzlich in einer Zivilsache entschieden hat (Art. 75 i.V.m. <ref-law>). Die Rechtsbegehren der Beschwerdeführer sind im kantonalen Verfahren nicht geschützt worden (<ref-law>), der massgebende Streitwert beträgt mehr als Fr. 15'000.-- (Art. 51 i.V.m. <ref-law>) und die Beschwerdefrist ist eingehalten (<ref-law>). Auf die Beschwerde ist daher unter Vorbehalt einer rechtsgenüglichen Begründung (Art. 42 Abs. 2 i.V.m. <ref-law>) einzutreten.
1.1 Die Beschwerde richtet sich gegen einen verfahrensabschliessenden Entscheid (<ref-law>) einer oberen kantonalen Instanz, die auf ein Rechtsmittel hin kantonal letztinstanzlich in einer Zivilsache entschieden hat (Art. 75 i.V.m. <ref-law>). Die Rechtsbegehren der Beschwerdeführer sind im kantonalen Verfahren nicht geschützt worden (<ref-law>), der massgebende Streitwert beträgt mehr als Fr. 15'000.-- (Art. 51 i.V.m. <ref-law>) und die Beschwerdefrist ist eingehalten (<ref-law>). Auf die Beschwerde ist daher unter Vorbehalt einer rechtsgenüglichen Begründung (Art. 42 Abs. 2 i.V.m. <ref-law>) einzutreten.
1.2 1.2.1 Mit Beschwerde in Zivilsachen können Rechtsverletzungen gemäss Art. 95 und 96 BGG gerügt werden. Die Beschwerde ist hinreichend zu begründen, andernfalls wird darauf nicht eingetreten. In der Beschwerdeschrift ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>). Eine qualifizierte Rügepflicht gilt hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht. Das Bundesgericht prüft solche Rügen nur insofern, als sie in der Beschwerde präzise vorgebracht und begründet worden sind (<ref-law>; <ref-ruling> E. 1.4.2. S. 254; <ref-ruling> E. 6, 439 E. 3.2).
Unerlässlich ist im Hinblick auf <ref-law>, dass die Beschwerde auf die Begründung des angefochtenen Entscheids eingeht und im Einzelnen aufzeigt, worin eine Verletzung von Bundesrecht liegt. Die beschwerdeführende Partei soll in der Beschwerdeschrift nicht bloss die Rechtsstandpunkte, die sie im kantonalen Verfahren eingenommen hat, erneut bekräftigen, sondern mit ihrer Kritik an den als rechtsfehlerhaft erachteten Erwägungen der Vorinstanz ansetzen (vgl. <ref-ruling> E. 2.1 S. 245 f.; <ref-ruling> E. 2a S. 400; <ref-ruling> E. 3 S. 749).
1.2.2 Diese Grundsätze verkennen die Beschwerdeführer in mehrfacher Hinsicht. So werfen sie der Vorinstanz überspitzten Formalismus und Rechtsverweigerung (<ref-law>) vor, da diese einige Urkunden als unzulässige Noven qualifiziert und damit nicht berücksichtigt habe, ohne diese Rügen überhaupt näher zu begründen. Weiter behaupten sie eine Verletzung des rechtlichen Gehörs (<ref-law>) und wiederum eine Rechtsverweigerung mit dem blossen Einwand, die Vorinstanz sei ihrer in der Berufung dargelegten Auffassung nicht gefolgt. Den Begründungsanforderungen genügt auch nicht, die Ausführungen der Vorinstanz darzulegen, um dann in einem Satz diverse Rechtsverletzungen zu behaupten, welche die Vorinstanz damit begangen haben soll. Auf solche Rügen ist nicht einzutreten.
1.2.2 Diese Grundsätze verkennen die Beschwerdeführer in mehrfacher Hinsicht. So werfen sie der Vorinstanz überspitzten Formalismus und Rechtsverweigerung (<ref-law>) vor, da diese einige Urkunden als unzulässige Noven qualifiziert und damit nicht berücksichtigt habe, ohne diese Rügen überhaupt näher zu begründen. Weiter behaupten sie eine Verletzung des rechtlichen Gehörs (<ref-law>) und wiederum eine Rechtsverweigerung mit dem blossen Einwand, die Vorinstanz sei ihrer in der Berufung dargelegten Auffassung nicht gefolgt. Den Begründungsanforderungen genügt auch nicht, die Ausführungen der Vorinstanz darzulegen, um dann in einem Satz diverse Rechtsverletzungen zu behaupten, welche die Vorinstanz damit begangen haben soll. Auf solche Rügen ist nicht einzutreten.
1.3 1.3.1 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Zu dem von der Vorinstanz grundsätzlich verbindlich festgestellten Sachverhalt gehören nicht nur die Feststellungen über den Lebenssachverhalt, der dem Streitgegenstand zugrunde liegt, sondern auch jene über den Ablauf des vorinstanzlichen Verfahrens und von diesem vorangegangenen Verfahren, wie namentlich die Parteivorbringen in denselben, also die Feststellungen über den Prozesssachverhalt (Urteile 4A_210/2009 vom 7. April 2010 E. 2; 4A_439/2010 vom 20. Oktober 2011 E. 2.1). Das Bundesgericht kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 1.2.2). Überdies muss die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein (<ref-law>). Die beschwerdeführende Partei, welche die Sachverhaltsfeststellungen der Vorinstanz anfechten will, muss klar und substanziiert aufzeigen, inwiefern die gerügten Feststellungen bzw. die Unterlassung von Feststellungen offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen (vgl. <ref-ruling> E. 1.4.3; <ref-ruling> E. 1.3, 393 E. 7.1, 462 E. 2.4). Auf eine Kritik an den tatsächlichen Feststellungen der Vorinstanz, die diesen Anforderungen nicht genügt, ist nicht einzutreten (<ref-ruling> E. 1.4.3), ebenso wenig auf Vorbringen, die in den tatsächlichen Feststellungen der Vorinstanz keine Stütze finden, ohne dass dazu eine taugliche Sachverhaltsrüge im vorstehenden Sinne substanziiert wird, oder auf Rügen, die auf solchen Vorbringen aufbauen.
1.3.2 Auch diese Grundsätze verkennen die Beschwerdeführer, wenn sie eine Verletzung von <ref-law> mit der Begründung rügen, der Beschwerdegegner 2 habe gar nie eine Mahnung erhalten. Denn weder geht solches aus dem vorinstanzlichen Urteil hervor noch bringen die Beschwerdeführer eine den Begründungsanforderungen genügende Rüge vor, wonach die vorinstanzlichen Sachverhaltsfeststellungen in dieser Hinsicht zu ergänzen seien.
Dasselbe gilt für die Rüge, die Vorinstanz habe <ref-law> falsch angewendet. Die Beschwerdeführer machen geltend, sie hätten die Kündigung fristgerecht bei den Schlichtungsbehörden angefochten, womit nach Aufhebung des aArt. 274g OR diese allein zuständig sei, die Gültigkeit der Kündigung zu beurteilen. Der Vermieter könne daher aufgrund der bestehenden Rechtshängigkeit des Schlichtungsverfahrens kein summarisches Ausweisungsverfahren einleiten, womit auch kein klarer Fall i.S.v. <ref-law> vorgelegen habe. Aus den vorinstanzlichen Sachverhaltsfeststellungen geht indessen weder hervor, dass die Kündigung angefochten wäre noch dass überhaupt ein Verfahren vor den Schlichtungsbehörden hängig wäre. Die Beschwerdeführer bringen auch in diesem Punkt keine Sachverhaltsrüge vor, wonach die vorinstanzlichen Feststellungen zu ergänzen wären. Ihr Vorbringen findet damit keine Stütze in den tatsächlichen Feststellungen, womit darauf nicht einzutreten ist.
2. Die Beschwerdeführer rügen weiter, der Beschwerdeführer 2 sei nicht passivlegitimiert, was die Vorinstanz in Verletzung von <ref-law> nicht berücksichtigt habe, indem sie das entsprechende Vorbringen fälschlicherweise als Novum im Sinne dieser Bestimmung qualifiziert habe. Die Frage der Passivlegitimation stelle ein rechtliches Novum dar, welches nicht von <ref-law> erfasst werde. Die entscheidrelevanten Tatsachen, nämlich die Mietverträge, hätten bereits im erstinstanzlichen Verfahren vorgelegen. Da die Beschwerdeführer im erstinstanzlichen Verfahren noch nicht vertreten worden seien, dürften an die Begründungspflicht nicht allzu hohe Anforderungen gestellt werden.
2.1 Nach <ref-law> werden neue Tatsachen und Beweismittel im Berufungsverfahren nur noch berücksichtigt, wenn sie ohne Verzug vorgebracht werden (lit. a) und trotz zumutbarer Sorgfalt nicht schon vor erster Instanz vorgebracht werden konnten (lit. b). Von neuen Tatsachen zu unterscheiden sind neue rechtliche Begründungen. Diese werden von <ref-law> nicht erfasst und können mithin sowohl im Berufungsverfahren als auch noch vor Bundesgericht im Rahmen des Streitgegenstandes vorbracht werden (<ref-ruling> E. 4.1; <ref-ruling> E. 4.4 S. 34, je mit Hinweisen). Dies ergibt sich insbesondere aus dem Grundsatz der Rechtsanwendung von Amtes wegen.
Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist somit weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen und es kann eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen (vgl. <ref-ruling> E. 1.4.1 S. 254; <ref-ruling> E. 2.5 S. 262; <ref-ruling> E. 1.4 S. 140).
2.2 Die Vorinstanz hat ausgeführt, gemäss den erstinstanzlichen Feststellungen seien beide Parteien von einem Beitritt des Beschwerdeführers 2 zum Mietverhältnis ausgegangen. Der Beschwerdeführer 2 habe im Verfahren vor dem Obergericht ein Fristerstreckungsgesuch unterzeichnet sowie eine Stellungnahme mitunterzeichnet. Er mache nun erstmals geltend, nicht Partei des Mietvertrags zu sein. Ob die Parteien legitimiert seien, habe das Gericht vor Fällung eines Sachurteils im Rahmen der Rechtsanwendung von Amtes wegen zu prüfen, dies jedoch in den Schranken der Verhandlungs- bzw. Eventualmaxime. Der Beschwerdeführer 2 habe weder behauptet noch bewiesen, dass er dieses neue Vorbringen trotz zumutbarer Sorgfalt nicht schon vor erster Instanz hätte geltend machen können. Das Vorbringen sei somit nach <ref-law> nicht zu berücksichtigen.
2.3 Die Beschwerdeführer richteten sich mit ihrer Rüge gegen die Feststellung des erstinstanzlichen Gerichts, wonach sowohl die Beschwerdeführer als auch die Beschwerdegegnerin von einem Beitritt des Beschwerdeführers 2 zum Mietverhältnis ausgingen. Nach Ansicht der Beschwerdeführer handelt es sich dabei um eine falsche rechtliche Würdigung. Die Beschwerdeführer übersehen aber, dass dieser Feststellung, welche die Vorinstanz übernommen hat, nicht eine Rechts-, sondern eine Tatfrage zugrunde liegt. Wenn das Gericht ausführt, beide Parteien gingen von einem Beitritt des Beschwerdeführers 2 zum Mietverhältnis aus, so stellt es damit den übereinstimmenden tatsächlichen Willen der Parteien über den Vertragsbeitritt fest. Dies stellt eine Sachverhaltsfeststellung dar, welche für das Bundesgericht grundsätzlich verbindlich ist (<ref-law>; vgl. <ref-ruling> E. 3.2 S. 413; <ref-ruling> E. 2.3.2). Gegen diese Feststellung des Parteiwillens bringen die Beschwerdeführer keine Sachverhaltsrügen vor. Ausgehend von diesen Sachverhaltsfeststellungen ist nicht ersichtlich, inwiefern der Beschwerdeführer 2 zu Unrecht als passivlegitimiert qualifiziert worden wäre. Damit erweist sich die Beschwerde in diesem Punkt als unbegründet.
3. Die Beschwerdeführer rügen weiter eine Verletzung von Art. 257e Abs. 2 und Art. 1 OR, indem die Vorinstanz einen konkludent zustande gekommenen neuen Mietvertrag verneint habe. Die Beschwerdegegnerin hätte die Zahlungen der Beschwerdeführer vom 20. Mai 2011, welche diese zur Begleichung der Mietzinsen bis Ende Jahr vorgenommen hätten, als Sicherheitsleistung entgegengenommen, was gegen <ref-law> verstosse, wonach Mietzinskautionen von maximal 3 Monatsmieten zulässig seien. Indem die Beschwerdegegnerin diese Zahlungen trotzdem angenommen habe, müsse von einem konkludent zustande gekommenen Mietvertrag ausgegangen werden.
3.1 Das Zustandekommen eines Vertrags bestimmt sich, wie sein Inhalt, in erster Linie durch subjektive Auslegung, das heisst nach dem übereinstimmenden wirklichen Parteiwillen. Wenn dieser unbewiesen bleibt, sind zur Ermittlung des mutmasslichen Parteiwillens die Erklärungen der Parteien aufgrund des Vertrauensprinzips so auszulegen, wie sie nach ihrem Wortlaut und Zusammenhang sowie den gesamten Umständen verstanden werden durften und mussten (<ref-ruling> E. 3.2; <ref-ruling> E. 1a S. 73; <ref-ruling> E. 1b; <ref-ruling> E. II/5a; vgl. auch <ref-ruling> E. 4 S. 27 f.; <ref-ruling> E. 4.1 S. 611).
3.2 Die Vorinstanz hat ausgeführt, die Beschwerdegegnerin habe umgehend ein Ausweisungsgesuch eingereicht, nachdem die Beschwerdeführer die Mieträumlichkeiten nicht geräumt übergeben hätten. Nach den Zahlungen der Beschwerdeführer am 20. Mai 2011 habe sie nicht erkennbar und vorbehaltlos auf die Rückgabe der Mieträumlichkeiten verzichtet. Vielmehr habe sie am 30. Mai 2011 dem erstinstanzlichen Gericht ausdrücklich mitgeteilt, dass sie am Ausweisungsbegehren festhalte. Es sei folglich nicht bewiesen, dass durch konkludentes Verhalten der Beschwerdegegnerin ein neuer Mietvertrag zustande gekommen sei. Die Annahme der Zahlung vom 20. Mai 2011 könne nach Ansicht der Beschwerdegegnerin als Annahme einer freiwillig geleisteten Sicherheit oder als Verrechnungssubstrat qualifiziert werden.
3.3 Die Ausführungen der Vorinstanz sind nicht zu beanstanden. Die Beschwerdegegnerin hat klar kommuniziert, dass sie am Ausweisungsgesuch festhält, womit sich die Beschwerdeführer zu keiner Zeit im Glauben befinden durften, die Parteien hätten einen neuen Mietvertrag geschlossen. Daran vermag auch der Umstand nichts zu ändern, dass die Beschwerdegegnerin die als Begleichung von Mietzinsen gedachte Zahlung der Beschwerdeführer vom 20. Mai 2011 diesen nicht umgehend rückerstattet hat. Ob die Beschwerdegegnerin Anspruch auf Rückbehaltung des gesamten Betrags hat oder die Beschwerdeführer allenfalls Anspruch auf Rückerstattung eines Teils oder des gesamten Betrags haben, ist nicht Gegenstand des vorliegenden Streits und daher nicht zu prüfen. Die Beschwerde erweist sich damit auch in diesem Punkt als unbegründet.
4. Nach dem Gesagten ist die Beschwerde abzuweisen, soweit darauf einzutreten ist. Bei diesem Verfahrensausgang werden die Beschwerdeführer unter solidarischer Haftbarkeit kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und 5 sowie Art. 68 Abs. 2 und 4 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern (unter solidarischer Haftbarkeit und intern zu gleichen Teilen) auferlegt.
3. Die Beschwerdeführer haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren (unter solidarischer Haftbarkeit und intern zu gleichen Teilen) mit Fr. 3'500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Luzern, 1. Abteilung, schriftlich mitgeteilt.
Lausanne, 28. November 2011
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Die Gerichtsschreiberin: Schreier