Aus den Erwägungen:
5.1 Aus dem eingereichten Strafregisterauszug für Privatpersonen vom 15. Dezember 2010 ist in der Tat ersichtlich, dass der Beschwerdeführer 1 sowohl mit Urteil des Amtsgerichts Hochdorf vom 27. Januar 2003 wie auch mit Urteil des Obergerichts des Kantons Luzern vom 22. September 2005 wegen rechtswidrigen Aufenthalts zu insgesamt drei Monaten Gefängnis verurteilt wurde. Beide Einträge werden noch bis 2. August 2012 im Strafregisterauszug für Privatpersonen erscheinen.
5.2 Das Justiz- und Sicherheitsdepartement hat sich mit der Frage der Folgen und der Würdigung von Strafregistereinträgen im Rahmen der Erteilung einer Aufenthaltsbewilligung aus humanitären Gründen bis anhin noch nicht befassen müssen.
5.2.1 Bei Gesuchen um eine Niederlassungsbewilligung gilt die Praxis, dass Niederlassungsbewilligungen solange nicht erteilt werden, als im Strafregister Vorstrafen eingetragen sind (vgl. LGVE 2004 III Nr. 4). Davon ausgehend ist die Vorinstanz zum Schluss gekommen, dass die gegen den Beschwerdeführer 1 im Strafregister verzeichneten Vergehen auch der Erteilung einer Aufenthaltsbewilligung aus humanitären Gründen entgegenstehen. Dieser Ansicht ist grundsätzlich beizupflichten. Es erscheint durchaus sinnvoll, die für die Erteilung der Niederlassungsbewilligung gültige Praxis auf Härtefallgesuche anzuwenden, sind doch die Hürden für die Erteilung einer Aufenthaltsbewilligung aus humanitären Gründen mit denjenigen für eine Erteilung einer Niederlassungsbewilligung vergleichbar. Der Grundsatz, dass Ausländerinnen und Ausländern bei Vorliegen von Strafregistereinträgen keine Härtefallbewilligung erteilt wird, ist demnach nicht zu beanstanden.
5.2.2 Im vorliegenden Fall ist allerdings zu beachten, dass den beiden Strafregistereinträgen Verurteilungen wegen Vergehen gegen das Ausländerrecht, konkret wegen illegalen Aufenthaltes, zugrunde liegen. Es stellt sich daher die Frage, ob solche Verurteilungen allein zur Abweisung eines Gesuches um Erteilung einer Aufenthaltsbewilligung aus humanitären Gründen führen dürfen. Das ist zu verneinen. Delikte im Bereich des Ausländerrechts sind zwar grundsätzlich den übrigen Straftaten gleichzustellen. Bei Bestrafungen wegen illegalen Aufenthaltes sowie illegaler Einreise drängt sich jedoch eine andere Würdigung auf, geht doch einem Gesuch um Erteilung einer Härtefallbewilligung oft ein illegaler Aufenthalt oder eine illegale Einreise voraus, namentlich wenn dieses von einer vorläufig aufgenommenen Person oder nach der Abweisung eines Asylgesuchs gestellt wird. Ferner ist es durchaus vom Zufall abhängig, ob es deswegen - beispielsweise aufgrund einer Strafanzeige - zu einer strafrechtlichen Verurteilung kommt oder nicht. Diese Umstände rechtfertigen es, diese Delikte besonders zu würdigen und ihnen im Rahmen der Erteilung von Aufenthaltsbewilligungen aus humanitären Gründen keine entscheidende Bedeutung beizumessen. (Justiz- und Sicherheitsdepartement, 13. September 2011)