Sachverhalt:
A. C._ (Vermieter, Beklagter, Beschwerdegegner) vermietet A. und B. X._ (Mieter, Kläger, Beschwerdeführer) seit dem 1. Januar 1992 eine 4.5-Zimmer-Wohnung in Y._. Die Mieter hatten auf ihrem Gartensitzplatz eine Satellitenschüssel und eine Vorrichtung für deren Montage installiert. Im Sommer 2009 verlangte der Vermieter die Entfernung dieser Satellitenschüssel und drohte den Mietern im Unterlassungsfall die fristlose Kündigung nach <ref-law> an. Diese demontierten darauf die Satellitenschüssel.
B. B.a Am 18. Dezember 2009 reichten die Mieter beim Amtsgericht Luzern-Stadt Klage ein mit dem Begehren, es sei festzustellen, dass sie berechtigt seien, auf dem mit der 4.5-Zimmer-Wohnung in Y._ zusammen gemieteten Gartensitzplatz eine Satellitenschüssel aufzustellen.
Mit Urteil vom 21. Oktober 2010 wies das Amtsgericht Luzern-Stadt die Feststellungsklage ab.
B.b Dagegen erhoben die Kläger Appellation beim Obergericht des Kantons Luzern. Sie ersuchten um Aufhebung des Urteils des Amtsgerichts und wiederholten ihr Feststellungsbegehren.
Mit Urteil vom 11. Juli 2011 wies das Obergericht die Appellation ab.
C. Mit Beschwerde in Zivilsachen vom 12. September 2011 beantragen die Kläger dem Bundesgericht, es sei das vorinstanzliche Urteil aufzuheben und es sei festzustellen, dass sie berechtigt seien, auf dem zusammen mit der 4.5-Zimmer-Wohnung in Y._ gemieteten Gartensitzplatz eine Satellitenschüssel aufzustellen.
Der Beschwerdegegner und die Vorinstanz beantragen die Abweisung der Beschwerde, soweit darauf einzutreten ist.
D. Mit Präsidialverfügung vom 17. Januar 2012 wurde der Vertreter der Beschwerdeführer aufgefordert, bis zum 3. Februar 2012 eine von diesen unterzeichnete Vollmacht einzureichen. Dieser Aufforderung kam der Vertreter der Beschwerdeführer fristgerecht nach.

Erwägungen:
1. Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (<ref-ruling> E. 1; <ref-ruling> E. 1, 101 E. 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 (Art. 100 Abs. 1 i.V.m. <ref-law>). Auf die Beschwerde ist somit unter Vorbehalt einer hinreichenden Begründung (Art. 42 Abs. 2 i.V.m. <ref-law>) einzutreten.
2. 2.1 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es 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).
Wird Willkür in der Ermittlung des Sachverhalts geltend gemacht, ist zu beachten, dass dem Sachrichter in der Beweiswürdigung ein breiter Ermessensspielraum zusteht; die beschwerdeführende Partei hat daher darzulegen, inwiefern das kantonale Gericht sein Ermessen missbraucht, insbesondere offensichtlich unhaltbare Schlüsse gezogen, erhebliche Beweise übersehen oder willkürlich ausser Acht gelassen habe (vgl. <ref-ruling> E. 2.1; <ref-ruling> E. 2.1; <ref-ruling> E. 4b S. 40; <ref-ruling> E. 1b S. 30). Auf eine Kritik an den tatsächlichen Feststellungen der Vorinstanz, die diesen Anforderungen nicht genügt, namentlich auf bloss appellatorische Vorbringen, ist nicht einzutreten (<ref-ruling> E. 1.4.3, 396 E. 3.1 S. 399).
2.2 Diese Grundsätze verkennen die Beschwerdeführer in mehrfacher Hinsicht:
2.2.1 In der Beschwerde wird der Sachverhalt aus der Sicht der Beschwerdeführer detailliert dargelegt. Soweit die Beschwerdeführer dabei von den vorinstanzlichen Feststellungen abweichen oder diese erweitern, ohne eine diesbezügliche Sachverhaltsrüge im vorstehenden Sinn zu erheben, sind sie damit nicht zu hören.
2.2.2 Die Beschwerdeführer rügen die vorinstanzliche Beweiswürdigung in verschiedenen Punkten als willkürlich. Sie bringen insbesondere vor, es treffe nicht zu, dass es sich beim Parabolspiegel, zu dessen Montage die Hausverwaltung ihr Einverständnis gegeben hatte, um eine kleinere Antenne für den Balkon gehandelt habe. Die Bezeichnung Parabolspiegel sei vielmehr ein Synonym für Satellitenschüssel. Die Hausverwaltung habe lediglich eine Bestätigung über die Störungsfreiheit der Satellitenschüssel gewünscht und sei mit der erneuten Montage durch ein Fachgeschäft einverstanden gewesen. Bei diesen Vorbringen setzen sich die Beschwerdeführer indessen nicht mit den Ausführungen der Vorinstanz auseinander, wonach die Hausverwaltung mehrfach auf <ref-law> hingewiesen habe und der Wortlaut eines Schreibens der Hausverwaltung darauf hindeute, dass die Montage einer kleineren Antenne erlaubt wurde, nicht hingegen die erneute Montage der Satellitenschüssel auf dem Gartensitzplatz. Auch bei ihren übrigen Rügen beschränken sich die Beschwerdeführer weitgehend auf die Darlegung ihrer eigenen Sichtweise. Damit genügen sie den Begründungsanforderungen nicht, weshalb auf diese Rügen nicht einzutreten ist.
3. Die Beschwerdeführer rügen weiter eine Verletzung des rechtlichen Gehörs aus zwei Gründen.
3.1 Erstens habe die Vorinstanz ihnen die Appellationsantwort des Beschwerdegegners lediglich zur Kenntnisnahme zugestellt und ihnen keine Gelegenheit zur Stellungnahme gegeben.
3.1.1 Gemäss <ref-law> und Art. 6 Ziff. 1 EMRK haben die Parteien eines Gerichtsverfahrens Anspruch auf rechtliches Gehör. Diese Garantie umfasst auch das Recht, von den beim Gericht eingereichten Stellungnahmen Kenntnis zu erhalten und sich dazu äussern zu können (sog. Replikrecht: <ref-ruling> E. 2.3.1; <ref-ruling> E. 2.1 S. 99). Eine neu eingegangene Eingabe wird den Parteien häufig ohne ausdrücklichen Hinweis auf allfällige weitere Äusserungsmöglichkeiten zur (blossen) Kenntnisnahme übermittelt. Kommen Verfahrensbeteiligte, welche eine solche Eingabe ohne Fristansetzung erhalten haben, zum Schluss, sie möchten nochmals zur Sache Stellung nehmen, so sollen sie dies aus Gründen des Zeitgewinns tun, ohne vorher darum nachzusuchen. Nach Treu und Glauben hat dies jedoch umgehend zu erfolgen (<ref-ruling> E. 4.8, 98 E. 2.2 S. 100).
3.1.2 Die Beschwerdeführer bestreiten nicht, dass die Vorinstanz ihnen die Appellationsantwort des Beschwerdegegners vom 9. Februar 2011 zugestellt hat. Es war ihnen freigestellt, dem Gericht umgehend eine Stellungnahme dazu einzureichen. Das vorinstanzliche Urteil erging erst am 11. Juli 2011, so dass den Beschwerdeführern dazu genügend Zeit zur Verfügung stand. Für die Wahrung des Anspruchs auf rechtliches Gehör ist nicht erforderlich, dass das Gericht bei jeder Zustellung einer Eingabe der Parteien explizit eine Frist zur Stellungnahme ansetzt. Die Rüge ist unbegründet.
3.2 Zweitens rügen die Beschwerdeführer als Verletzung des rechtlichen Gehörs, dass die Vorinstanz die Abnahme der mehrfach beantragten Expertise über die Möglichkeiten zum Empfang ausländischer Fernsehprogramme verweigert habe. Aufgrund des Grundrechtes auf Informationsfreiheit seien sie auch ohne Zustimmung der Vermieterschaft zur Installation der Satellitenschüssel berechtigt, falls sie keine andere Möglichkeit zum Empfang der Fernsehprogramme aus ihren heimatlichen Ländern Ägypten und Japan hätten. Da die Beschwerdeführer auf dem Gebiet der Kommunikationstechnik Laien seien, hätten sie sich in ihrer Rechtsschrift nicht mit allfälligen technischen Alternativen auseinandergesetzt. Diese Frage könne nur von einem Experten beantwortet werden.
3.2.1 Die Vorinstanz hat ausgeführt, mit Beweisanträgen könnten fehlende Substanziierungen nicht nachgeholt werden, da Beweiserhebungen schlüssige Vorbringen voraussetzten. Die Beschwerdeführer seien vom erstinstanzlichen Gericht aufgefordert worden, zur Behauptung des Beschwerdegegners Stellung zu nehmen, wonach die gewünschten ausländischen Fernsehprogramme mit alternativen technischen Vorrichtungen empfangen werden könnten. Trotz dieser Aufforderung hätten die Beschwerdeführer ihre Vorbringen nicht substanziiert, sondern bloss pauschal bestritten, dass die ägyptischen und japanischen Fernsehprogramme auch ohne Satellitenschüssel empfangen werden könnten. Selbst nachdem der Beschwerdegegner konkret alternative Empfangsmöglichkeiten aufgeführt habe, seien die Beschwerdeführer inhaltlich oberflächlich geblieben und hätten sich mit den genannten Alternativen kaum auseinandergesetzt. Unter diesen Umständen habe das erstinstanzliche Gericht zu Recht auf eine Expertise verzichtet.
3.2.2 Der Anspruch auf rechtliches Gehör (<ref-law>) gewährt den Parteien insbesondere das Recht, mit rechtzeitig und formrichtig angebotenen erheblichen Beweismitteln gehört zu werden (<ref-ruling> E. 5.3; <ref-ruling> E. 2.2; <ref-ruling> E. 2b). Keine Verletzung des rechtlichen Gehörs liegt vor, wenn ein Gericht darauf verzichtet, beantragte Beweise abzunehmen, weil es aufgrund bereits abgenommener Beweise seine Überzeugung gebildet hat und ohne Willkür in vorweggenommener Beweiswürdigung annehmen kann, dass seine Überzeugung durch weitere Beweiserhebungen nicht geändert würde (<ref-ruling> E. 5.3; <ref-ruling> E. 2.1 mit Hinweisen).
Das Bundesgericht greift in eine antizipierte Beweiswürdigung nur ein, wenn sie willkürlich und damit offensichtlich unhaltbar ist, namentlich wenn sie eine prozessuale Vorschrift oder einen unumstrittenen Grundsatz des Beweisrechts krass verletzt oder sonst wie in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 2.1; <ref-ruling> E. 3 S. 157, 217 E. 2.1; <ref-ruling> E. 2.1; <ref-ruling> E. 4a). Die Verletzung von Grundrechten kann das Bundesgericht zudem nur insofern prüfen, als eine solche Rüge in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>; <ref-ruling> E. 1.4.2 S. 254; <ref-ruling> E. 6, 439 E. 3.2).
3.2.3 Diesen Anforderungen genügen die Beschwerdeführer nicht. Mit der Argumentation der Vorinstanz zur Substanziierung der Vorbringen setzen sie sich nicht auseinander, sondern beschränken sich darauf, erneut auf ihre Eigenschaft als Laien im Gebiet der Kommunikationstechnik hinzuweisen. Es ist indessen ohnehin nicht ersichtlich, inwiefern die Vorinstanz bei ihren Ausführungen zur Ablehnung des Beweisantrages in Willkür verfallen wäre. Die Rüge ist damit unbegründet, soweit überhaupt darauf einzutreten ist.
4. Die Beschwerdeführer rügen schliesslich eine Verletzung von <ref-law>. Der zur Montage der Satellitenschüssel verwendete 0.57 Meter hohe Betonsockel mit einer Fläche von 0.24 x 0.24 Meter, welcher wenige Zentimeter in die Rasenfläche eingegraben worden sei, stelle keine bauliche Veränderung der Mietsache dar. Auch Sonnenschirme, eine Gartenbank oder Topfpflanzen würden zwecks Verbesserung der Stabilität in den Boden eingegraben. Es liege in der Natur der Sache, dass unter Mobilien, welche auf einer Rasenfläche abgestellt worden seien, nach deren Entfernung Grasnarben zurückbleiben würden, welche jedoch innert weniger Wochen wieder überwachsen seien. Eine ästhetische Beeinträchtigung liege zudem nicht vor, da die Satellitenschüssel unbestrittenermassen hinter einem Gebüsch versteckt gewesen sei und beim Passieren der Liegenschaft ausserhalb des Sitzplatzes nicht eingesehen werden könne.
4.1 Die Vorinstanz hat ausgeführt, die Beschwerdeführer hätten einen 0.57 m hohen Betonsockel von 0.24 m x 0.24 m aufgestellt bzw. in die Erde gegraben. Oben messe der Kranzring des Sockels 0.27 m x 0.27 m. Der Sockel sei hohl und mit Erde und Steinen gefüllt. Wie tief er eingegraben worden sei, habe sich am Augenschein des erstinstanzlichen Gerichts nicht eruieren lassen. Er stehe fest und lasse sich von zwei erwachsenen jungen Männern nicht heben, sondern lediglich geringfügig hin und her bewegen. Für die Montage der Satellitenschüssel werde ein rostiges Eisenrohr in den Betonsockel gesteckt, an dem diese festgeschraubt werden könne. Die Satellitenschüssel habe einen Durchmesser von 0.9 m und der obere Rand komme auf eine Höhe von rund 1.6 m.
Die Beschwerdeführer hatten vor der Vorinstanz vorgebracht, es hätte mit einer Schaufel die Erde um den Sockel abgetragen werden müssen, um ihn zu heben. Die Entfernung des Sockels hätte einen Arbeitsaufwand von etwa 10 bis 20 Minuten erfordert. Der Betonsockel, der hinter einem Busch verborgen gewesen sei, sei ähnlich wie das Aufstellen von Gartenmöbeln oder grösseren Topfpflanzen zu dulden. Darauf entgegnete die Vorinstanz, die Beschwerdeführer würden nicht bestreiten, dass das Loch nach Entfernung des Sockels mit Erde ausgefüllt und mit Gras bepflanzt werden müsse. Es sei irrelevant, innert welcher Zeit die Änderung rückgängig gemacht werden könne oder ob die Konstruktion hinter einem Busch verborgen sei. Der Vergleich mit Gartenmöbeln oder grösseren Topfpflanzen greife nicht, weil es sich dabei um frei bewegliche Gegenstände handle, die nicht mit der Mietsache verbunden seien. Das für den Sockel ausgegrabene Loch stelle einen Eingriff in die Substanz des Mietobjekts dar.
4.2 Nach <ref-law> kann der Mieter Erneuerungen und Änderungen an der Sache nur vornehmen, wenn der Vermieter schriftlich zugestimmt hat. Eine Änderung ist ein gewollter Eingriff in die Substanz der Mietsache, dessen Resultat in einer Abweichung der Gestaltung und des Zustandes der Mietsache vom bisher vertraglich vereinbarten Zustand und der bisherigen Gestaltung besteht (Urteil 4C.393/2002 vom 27. Mai 2003 E. 5.3; vgl. PETER HIGI, Zürcher Kommentar, 4. Aufl. 1994, N. 6 zu <ref-law>, N. 9 zu <ref-law>). Als Beispiele für Änderungen an der Sache werden in der Lehre etwa genannt die Montage eines textilen Belages auf einem Parkettboden et vice versa und Montage einer fixen Einrichtung anstelle einer beweglichen (HIGI, a.a.O., N. 7 zu <ref-law>), die Installation eines Telefonanschlusses (HIGI, a.a.O., N. 7 zu <ref-law>) oder das Pflanzen von Bäumen (DAVID LACHAT, Le bail à loyer, 2008, S. 827).
4.3 Nach den verbindlichen Feststellung der Vorinstanz haben die Beschwerdeführer den Betonsockel zur Montage der Satellitenschüssel in den Gartensitzplatz, der unbestrittenermassen zur Mietsache gehört, eingegraben. Wie tief er eingegraben wurde, konnte zwar nicht eruiert werden, doch war der Sockel jedenfalls so gut befestigt, dass er von zwei erwachsenen jungen Männern nicht gehoben, sondern lediglich geringfügig hin und her bewegt werden konnte. Dies trotz der eher bescheidenen Masse von 0.57 m x 0.27 m x 0.27 m. Die gesamte Konstruktion ist zudem rund 1.6 m hoch. Entgegen der Ansicht der Beschwerdeführer ist eine solche Konstruktion nicht mit Gartenmöbeln oder Topfpflanzen vergleichbar. Damit ist vielmehr ein Eingriff in die Substanz der Mietsache verbunden, der zu einer Änderung deren Gestaltung und Zustand führt. Die Vorinstanz hat somit <ref-law> nicht verletzt, indem sie die Montage des Betonsockels mit Satellitenschüssel als Änderung im Sinne dieser Bestimmung qualifiziert hat. Die Rüge ist unbegründet.
5. 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. 2'000.-- werden den Beschwerdeführern (unter solidarischer Haftbarkeit und intern zu gleichen Teilen) auferlegt.
3. Die Beschwerdeführer haben den Beschwerdegegner für das bundesgerichtliche Verfahren (unter solidarischer Haftbarkeit und intern zu gleichen Teilen) mit Fr. 2'500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Luzern, 1. Abteilung, schriftlich mitgeteilt.
Lausanne, 28. März 2012
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Die Gerichtsschreiberin: Schreier