Sachverhalt:
A. Y._ meldete sich am 11. September 1996 auf der Gemeinde G._ als unter der Adresse _ Niedergelassene an. Am 3. Juli 2000 meldete sich auch ihr Ehemann mit derselben Adresse an. Nachdem die Einwohnerkontrolle G._ im Februar 2006 davon Kenntnis erhalten hatte, dass Y._ und X._ an dieser Adresse nie eine Wohnung gemietet hatten, sondern dort lediglich über eine Briefkastenadresse verfügten, meldete sie das Ehepaar am 22. September 2006 "nach unbekannt" ab. Am 5. Februar 2007 hinterlegte das Ehepaar X._-Y._ seine Schriften bei der Einwohnerkontrolle der Stadt Luzern. Das zuvor gestellte Gesuch, die Abmeldung rückgängig zu machen, erklärte der Gemeinderat G._ am 29. März 2007 mangels rechtserheblichen Interesses als erledigt.
Das Justiz- und Sicherheitsdepartement des Kantons Luzern hiess die von Y._ und X._ dagegen gerichtete Beschwerde im Umfang des Eintretens gut und stellte fest, der Entscheid des Gemeinderates vom 29. März 2007 sei nichtig, soweit er feststelle, der Wohnsitz der Beschwerdeführer befinde sich nicht in G._; eine solche Feststellung sei nur im Zusammenhang mit einer konkreten Streitfrage möglich, welche an den Wohnsitz anknüpfe.
Auf Beschwerde der Gemeinde G._ hob das Verwaltungsgericht des Kantons Luzern diesen Entscheid auf und stellte fest, dass die registerrechtliche Abmeldung aus der Gemeinde G._ rechtmässig sei.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 12. Januar 2009 beantragen Y._ und X._ dem Bundesgericht, das Urteil des Verwaltungsgerichts des Kantons Luzern vom 9. Dezember 2008 aufzuheben und ihr Niederlassungsrecht zu schützen bzw. wiederherzustellen.
Es wurden keine Vernehmlassungen eingeholt.

Erwägungen:
1. 1.1 Soweit die Beschwerdeführer auf Eingaben im kantonalen Verfahren verweisen, ist darauf nicht einzutreten (<ref-law>; Urteil 4A_137/2007 vom 20. Juli 2007 E. 4; vgl. <ref-ruling> E. 2.3).
1.2 Die Vorinstanz hat erkannt, Streitgegenstand bilde nicht der zivilrechtliche Wohnsitz, sondern der melderechtliche und damit die öffentlich-rechtliche Niederlassung bzw. das polizeiliche Domizil der Beschwerdeführer. Anwendbar sei daher das kantonale Gesetz vom 1. Dezember 1948 über die Niederlassung und den Aufenthalt sowie über die Zwangsmassnahmen im Ausländerrecht (NG/LU) bzw. das Bundesgesetz vom 23. Juni 2006 über die Harmonisierung der Einwohnerregister und anderer amtlicher Personenregister (Registerharmonisierungsgesetz, RHG; SR 431.02).
1.3 Wer in einer Gemeinde des Kantons Luzern Wohnsitz nimmt oder dort länger als zwei Monate verweilen will, hat zur Begründung der Niederlassung binnen zehn Tagen Ausweisschriften abzugeben (§§ 3 und 4 NG/LU); dasselbe gilt für Aufenthalter (§ 5 NG/LU). Die Gemeinden sind verantwortlich, dass diese Bestimmungen eingehalten werden (§ 13 und 16 NG/LU), und haben die Ausweisschriften bei den Säumigen einzufordern; diese können nach erfolgloser Verwarnung und Bestrafung aus der Gemeinde weggewiesen werden (Art. 18 NG/LU).
In analoger Anwendung von Art. 3 lit. b und c RHG erachtet die Vorinstanz im Einklang mit der Gemeinde G._ jene Gemeinde als Niederlassungsgemeinde, in der sich eine Person in der Absicht dauernden Verbleibens aufhält, um dort den Mittelpunkt ihres Lebens zu begründen, welcher für Dritte erkennbar sein muss; als Aufenthaltsgemeinde bezeichnet sie jene, in der sich eine Person zu einem bestimmten Zweck ohne Absicht dauernden Verbleibens mindestens während dreier Monate innerhalb eines Jahres aufhält. Für die polizeiliche Niederlassung seien somit Beziehungen von ausreichender Dauer und Intensität zum Ort der beabsichtigten Niederlassung unerlässlich. Auch die Niederlassungsfreiheit (<ref-law>) berechtige nicht, einen beliebigen Ort als Niederlassung zu bezeichnen, ohne dass die tatsächlichen Voraussetzungen dafür gegeben seien.
Mit diesen rechtlichen Ausführungen setzen sich die Beschwerdeführer nicht näher auseinander; es kann deshalb auf diese bundesrechtlich nicht zu beanstandende Darstellung im angefochtenen Entscheid verwiesen werden.
1.4 Die Vorinstanz hat festgestellt, dass sich die Beschwerdeführer in der Gemeinde G._ angemeldet hätten, ohne dort je Mieter oder Untermieter von bewohnbaren Räumen gewesen zu sein. Auch auf Nachfrage hätten sie nie über ihre tatsächlichen Wohnverhältnisse Auskunft gegeben. Eine Wohngelegenheit an der _ (Nächtigungsmöglichkeit bei ehemaligen Nachbarn) habe nie belegt werden können; es könne ausgeschlossen werden, dass die Beschwerdeführer während dreier Monate Gastrecht im Haushalt der ehemaligen Nachbarn beansprucht hätten. Die höchstens sporadischen Anwesenheiten vermöchten daher mangels der erforderlichen Intensität weder eine Niederlassung noch einen Aufenthalt zu begründen.
Die Beschwerdeführer legen nicht dar, dass und inwiefern diese tatsächlichen Feststellungen offensichtlich unrichtig wären oder auf einer Rechtsverletzung beruhten (Art. 97 Abs. 1 und 105 BGG); es ist daher auf sie abzustellen.
1.5 Unter diesen Umständen hat die Gemeinde nach Auffassung der Vorinstanz im Sinne einer Ersatzvornahme die ebenfalls zu den Meldepflichten zählende Abmeldung der Beschwerdeführer vornehmen dürfen. Die Massnahme erweise sich auch als verhältnismässig, da sie nicht rückwirkend verfügt und weder eine Busse noch eine Wegweisung ausgesprochen worden seien.
Was die Beschwerdeführer dagegen vorbringen, erschöpft sich in einer verkürzten Darstellung der eigenen Sicht der Dinge. Sie setzen sich indessen in keiner den Begründungsanforderungen von <ref-law> genügenden Weise mit dem angefochtenen Entscheid auseinander.
2. Die Beschwerde ist aus diesen Gründen abzuweisen, soweit überhaupt darauf einzutreten ist.
Da sich die gestellten Rechtsbegehren als von vornherein aussichtslos erwiesen haben, kann den Beschwerdeführern die unentgeltliche Rechtspflege nicht gewährt werden (<ref-law>). Entsprechend dem Ausgang haben sie die Kosten des Verfahrens vor Bundesgericht unter solidarischer Haftung zu tragen (Art. 66 Abs. 1 und 5 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um Gewährung der unentgeltlichen Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern auferlegt, unter solidarischer Haftung.
4. Dieses Urteil wird den Parteien und dem Verwaltungsgericht des Kantons Luzern schriftlich mitgeteilt.
Lausanne, 13. März 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Küng