Sachverhalt:
A. X._ (geb. 1963) ist spanischer Staatsangehöriger. Er zog am 18. Januar 1985 in die Schweiz und erhielt am 30. April 1990 eine Niederlassungsbewilligung (Kanton Freiburg). Am 15. November 1991 meldete er sich bei der Einwohnerkontrolle der Stadt Zug an und zog im September 1992 an die A._-strasse nach E._ (Kanton Zug). In E._ wechselte er in der Folge zweimal seine Wohnadresse; zuletzt zog er an die B._-strasse. Am 26. März 2004 beantragte X._ beim Sozialdienst der Gemeinde E._ Sozialhilfe und reichte dabei einen Untermietvertrag für die B._-strasse vom 30. September 2003 zwischen ihm als Untermieter und C._ als Untervermieter ein. Ab dem 25. August 2004 erhielt er die beantragte Sozialhilfe; die Gemeinde stützte sich für deren Erteilung u.a. auf den Untermietvertrag mit C._. Am 31. Oktober 2005 meldete sich C._ definitiv in E._ ab und gab an, inskünftig in Spanien zu wohnen.
Die Kontrollfrist für die Niederlassungsbewilligung von X._ wurde mehrmals verlängert. Am 6. Juli 2007 bestätigte das Bundesgericht die Ablehnung eines Antrags um Zusprechung einer IV-Rente. Am 26. November 2008 ersuchte X._ um eine weitere Verlängerung der Kontrollfrist seiner Niederlassungsbewilligung, dabei gab er als Wohnadresse die B._-strasse in E._ und als Zweck des Aufenthalts "nichterwerbstätig, IV-Abklärung" an. Im Dezember 2009 stellte die Gemeinde E._ fest, dass die Wohnung an der B._-strasse seit dem 17. April 2005 an andere Personen vermietet war. Die Gemeinde orientierte hierüber das Amt für Migration des Kantons Zug. In einem Telefongespräch erteilte sie diesem zudem die Auskunft, dass X._ nie eine neue Adresse gemeldet, jedoch Sozialgelder in der Gemeinde bezogen habe. X._ habe diesen Umstand auf Rückfrage hin damit erklärt, dass C._ ihm fristlos gekündigt habe, worauf er in einer Notwohnung einquartiert worden sei.
Das Amt für Migration des Kantons Zug befragte X._ am 14. Januar 2010 zu seiner Wohnsituation. Die Erkenntnisse der Befragung wurden der Gemeinde E._ mitgeteilt. Diese erhob gegen X._ eine Strafanzeige wegen Betrugs (<ref-law>) sowie unrechtmässigen Erwirkens von Leistungen (§ 41bis des Gesetzes über die Sozialhilfe im Kanton Zug vom 16. Dezember 1982). Am 5. Mai 2010 teilte das kantonale Migrationsamt X._ mit, seine Niederlassungsbewilligung sei per 30. Juni 2006 erloschen: Das Migrationsamt sah es als erwiesen an, dass dieser vom 17. April 2005 bis Ende 2009 vorwiegend landesabwesend gewesen und nur noch besuchsweise in die Schweiz eingereist sei.
B. Gegen diese Verfügung erhob X._ erfolglos Beschwerde beim Regierungsrat des Kantons Zug. Eine gegen diesen Entscheid gerichtete Beschwerde an das Verwaltungsgericht des Kantons Zug wies dieses mit Urteil vom 27. März 2012 ab.
C. Mit Eingabe vom 15. Mai 2012 erhebt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht und beantragt, der Entscheid des Verwaltungsgerichts des Kantons Zug sei aufzuheben; ihm sei die Niederlassungsbewilligung zu belassen. Eventuell sei die Sache bezüglich der Erteilung einer Aufenthaltsbewilligung an die Vor- oder erste Instanz zurückzuweisen. X._ ersucht um unentgeltliche Prozessführung und Verbeiständung.
Das Verwaltungsgericht des Kantons Zug beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Es weist darauf hin, dass die Frage des Erlöschens der Niederlassungsbewilligung infolge Landesabwesenheit und ein allfälliger Sozialhilfemissbrauch zu trennen seien, weshalb es den Sozialhilfebezug konsequent aus seinem Urteil ausgeklammert habe. Der Eventualantrag (Prüfung eines allfälligen Aufenthaltsanspruchs) sei ohne Begründung erhoben worden, weshalb ihn das Verwaltungsgericht nicht habe behandeln können. Das Amt für Migration des Kantons Zug verzichtet auf eine umfassende Vernehmlassung, weist jedoch darauf hin, dass die Aktennotizen auf Post-it-Klebern zu Telefongesprächen in die Protokolle vom 14. Januar 2010 (Befragung zur Wohnsituation) Eingang gefunden hätten, sodass der Beschwerdeführer hiervon Kenntnis gehabt habe. Im Übrigen beantragt es die Abweisung der Beschwerde. Der Regierungsrat des Kantons Zug (Sicherheitsdirektion) weist darauf hin, bei der Meldung der Gemeinde an das kantonale Ausländeramt, wonach der Beschwerdeführer offenbar keinen Wohnsitz (mehr) an der von ihm gemeldeten Adresse habe, handle es sich nicht um eine Meldung hinsichtlich eines allfälligen missbräuchlichen Bezugs von Sozialhilfe; die Verfahren seien zu trennen. Der Gemeinde stehe es zu, das kantonale Ausländeramt über An- und Abmeldungen ausländischer Personen zu informieren. Es seien deshalb keine Datenschutzbestimmungen und Geheimhaltungsverpflichtungen verletzt worden. Das Bundesamt für Migration beantragt, die Beschwerde abzuweisen.
Mit Verfügung vom 23. Mai 2012 hat der Präsident der Beschwerde aufschiebende Wirkung zuerkannt.

Erwägungen:
1. 1.1 Auf dem Gebiet des Ausländerrechts ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen die Erteilung oder Verweigerung von Bewilligungen ausgeschlossen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumen (<ref-law>). Gegen Entscheide über den Widerruf oder die Feststellung des Erlöschens einer Niederlassungsbewilligung ist die Beschwerde jedoch zulässig, weil grundsätzlich ein Anspruch auf das Fortbestehen dieser Bewilligung gegeben ist (<ref-ruling> E. 1.2.1 S. 4). Der Beschwerdeführer kann sich als spanischer Staatsangehöriger zudem auf das Abkommen vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten andererseits über die Freizügigkeit berufen (FZA; SR 0.142.112.681). Gemäss Art. 2 Abs. 1 Anhang I FZA hat er das Recht, sich nach Massgabe der Kapitel II bis IV in der Schweiz aufzuhalten. Auf die Beschwerde ist demnach grundsätzlich einzutreten (vgl. jedoch die nachfolgenden Erwägungen E. 1.6 und 1.7).
1.2 Da das kantonale Migrationsamt die Überprüfung des Erlöschens der Niederlassungsbewilligung im Jahr 2009, also nach dem Inkrafttreten des AuG eingeleitet und dem Beschwerdeführer das rechtliche Gehör am 14. Januar 2010 gewährt hat, ist die Beschwerde - über den engen Wortlaut von Art. 126 Abs. 1 AuG hinaus - nach neuem Recht zu beurteilen (Urteil 2C_478/2010 vom 17. November 2010 E.1, nicht publ. in: <ref-ruling>; Urteil 2C_779/2011 vom 6. August 2012 E. 1.2; MARC SPESCHA, in: Spescha/Thür/Zünd/Bolzli [Hrsg.], Migrationsrecht, 3. Aufl. 2012, N. 1 zu Art. 126 AuG; PETER UEBERSAX, Einreise und Anwesenheit, in: Uebersax/Rudin/Hugi Yar/Geiser [Hrsg.], Ausländerrecht, 2. Aufl. 2009, N. 7.10).
1.3 Das Bundesgericht ist an die Sachverhaltsfeststellungen der Vorinstanz gebunden, soweit sie sich nicht als offensichtlich unrichtig, d.h. willkürlich erweisen oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen (Art. 105 Abs. 1 und 2 BGG; vgl. <ref-ruling> E. 4.1.2 S. 62; <ref-ruling> E. 1.2.2 S. 252; <ref-ruling> E. 7.1 S. 398). Zudem ist vom Beschwerdeführer aufzuzeigen, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>).
1.4 Bezüglich der Überprüfung und Anwendung von kantonalem Recht ist die Kognition des Bundesgerichts ausserhalb des Anwendungsbereichs von Art. 95 lit. c bis lit. e BGG beschränkt. Die Verletzung kantonaler bzw. kommunaler Bestimmungen bildet nur dann einen zulässigen Beschwerdegrund, wenn eine derartige Rechtsverletzung einen Verstoss gegen Bundesrecht im Sinne von <ref-law> - beispielsweise das Willkürverbot (<ref-law>) - oder gegen Völkerrecht im Sinne von <ref-law> zur Folge hat (<ref-ruling> E. 2.4 S. 249; <ref-ruling> E. 2.3 S. 466; <ref-ruling> E. 1.2.1 S. 251 f.).
1.5 Die Beschwerdeschrift hat gemäss <ref-law> die Begehren und deren Begründung zu enthalten; im Rahmen der Begründung ist in gedrängter Form darzulegen, inwiefern der angefochtene Entscheid Recht verletzt (<ref-law>). Dies setzt voraus, dass sich der Beschwerdeführer wenigstens kurz mit den Erwägungen des angefochtenen Entscheides auseinandersetzt (<ref-ruling> E. 2.1 S. 245 f.). Eine qualifizierte Rügepflicht gilt hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht (vgl. E. 1.4). Das Bundesgericht prüft eine solche Rüge nur insoweit, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>).
1.6 Gegenstand des ausländerrechtlichen Verfahrens bildet vorliegend die Frage, ob die Vorinstanzen zu Recht von einer erloschenen Niederlassungsbewilligung infolge längerer Landesabwesenheit des Beschwerdeführers ausgegangen sind (zur Frage des Aufenthaltsrechts vgl. unten E. 4.4). Demgegenüber ist die Frage, ob der Beschwerdeführer einen Sozialhilfebetrug begangen hat, hier nicht zu prüfen; dies ebenso wenig wie die Frage, ob die für das Strafverfahren erforderlichen Beweismittel korrekt erlangt wurden. Das vom Amt für Migration des Kantons Zug am 5. November 2012 dem Bundesgericht eingereichte strafrechtliche Urteil vom 17. Oktober 2012 (Verurteilung des Beschwerdeführers wegen Betrugs; <ref-law>) ist demnach nicht Verfahrensgegenstand. Im Übrigen handelt es sich um ein Novum (<ref-law>).
Als echte Noven unberücksichtigt bleiben die vom Beschwerdeführer herangezogenen Belege für Bargeldeinzahlungen. Sie sind bisher lediglich im strafrechtlichen Verfahren, nicht jedoch im Verfahren betreffend das Erlöschen der Niederlassungsbewilligung geltend gemacht worden (<ref-law>).
1.7 Nicht eingetreten werden kann auf die Beschwerde insoweit, als der Beschwerdeführer eine unrichtige Anwendung von Art. 30 Abs. 1 lit. k AuG rügt. Die Abweichungen von den Zulassungsvoraussetzungen entziehen sich gemäss dem Ausnahmekatalog der Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>); auf sie besteht überdies kein Rechtsanspruch (<ref-law>). Diesbezüglich werden auch keine Rügen substanziiert vorgetragen, die als subsidiäre Verfassungsbeschwerde entgegengenommen werden könnten.
2. Der Beschwerdeführer rügt eine Verletzung des rechtlichen Gehörs (<ref-law>).
2.1 Er bringt vor, das Akteneinsichtsrecht sei verletzt, indem ihm die Post-it-Zettel, auf denen Gesprächsnotizen festgehalten wurden, nie ausgehändigt worden seien. Diese seien auch nicht zu den Akten gelegt worden, wodurch die Dokumentationspflicht verletzt worden sei.
Der Beschwerdeführer hatte bereits vor der Vorinstanz beantragt, die Post-it-Zettel als Beweismittel nicht zuzulassen. Diese ist ihm in jenem Vorbringen gefolgt und hat ihre Ausführungen nicht auf die entsprechenden Anmerkungen, sondern vielmehr auf äussere Umstände wie die unklare Wohnsituation und die fehlende Substanziierung der Anwesenheit des Beschwerdeführers in der Schweiz gestützt. Eine Gehörsverletzung liegt somit nicht vor.
2.2 Der Beschwerdeführer wirft der Vorinstanz weiter vor, diverse seiner Ausführungen - namentlich zum Datenschutz - seien unberücksichtigt geblieben. Das Verwaltungsgericht sei zudem seiner Begründungspflicht nicht nachgekommen. Überdies sei er mit seinem Eventualantrag auf Erteilung einer Aufenthaltsbewilligung nicht gehört worden; dies komme einer Rechtsverweigerung gleich.
Aus dem Anspruch auf rechtliches Gehör nach <ref-law> folgt die grundsätzliche Pflicht der Behörde, ihren Entscheid zu begründen. Das bedeutet indessen nicht, dass sich die Behörde mit jeder tatbestandlichen Behauptung und jedem rechtlichen Einwand eingehend auseinandersetzen muss. Vielmehr kann sie sich auf die für den Entscheid wesentlichen Punkte beschränken. Die Rechtsuchenden sollen wissen, warum die Behörde gegen ihren Antrag entschieden hat, damit sie gegebenenfalls den Entscheid sachgerecht anfechten können (<ref-ruling> E. 4.1 S. 88; <ref-ruling> E. 3.1 S. 277 mit Hinweisen; Urteil 2C_476/2012 vom 30. Oktober 2012 E. 2.1).
Die Vorinstanz hat sich intensiv mit den Vorbringen des Beschwerdeführers in datenschutzrechtlicher Hinsicht auseinandergesetzt und dies auch vor dem Hintergrund der Eingriffe in die Privatsphäre des Beschwerdeführers getan; sie hat ihre Beurteilung des Informationsaustauschs unter Bezugnahme auf Art. 97 AuG und § 5 des Einführungsgesetzes zum Bundesgesetz über Aufenthalt und Niederlassung der Ausländer vom 28. November 1996 (EG ANAG [Kanton Zug]) auch ausreichend begründet. Welche weiteren Erwägungen unbegründet geblieben sein sollen, wird vom Beschwerdeführer nicht weiter belegt, sodass diesbezüglich keine Verletzung von <ref-law> dargetan ist.
Eine ausdrückliche Behandlung des Eventualantrags auf die Erteilung einer Aufenthaltsbewilligung findet sich in den Erwägungen der Vorinstanz hingegen nicht. Diese führt dazu in der Vernehmlassung aus, der Eventualantrag sei nicht explizit behandelt worden, weil er unbegründet geblieben sei, was der Beschwerdeführer nicht bestreitet. In materieller Hinsicht kann ein Verbleiberecht dem Erlöschen der Niederlassungsbewilligung infolge Landesabwesenheit von über 6 Monaten nicht entgegenstehen (dazu hinten E. 4.4), sodass die Vorinstanz dies nicht getrennt prüfen musste. Andere anspruchsbegründenden Tatsachen wie Erwerbstätigkeit in der Schweiz oder die Einreise zur Stellensuche oder auch ein erwerbsloser Aufenthalt sind unbestrittenermassen (auch) vor der Vorinstanz nicht vorgebracht worden. Das Vorgehen der Vorinstanz verletzt daher nicht den Anspruch des Beschwerdeführers auf rechtliches Gehör (<ref-law>) und stellt auch keine Rechtsverweigerung dar.
3. Der Beschwerdeführer rügt den Informationsaustausch zwischen seiner Wohngemeinde und dem kantonalen Migrationsamt. Die Gemeinde sei nicht ermächtigt gewesen, systematisch Daten der Einwohnerkontrolle an die Ausländerbehörde zu melden. Vielmehr regle Art. 97 AuG i.V.m. Art. 82 der Verordnung vom 24. Oktober 2007 über Zulassung, Aufenthalt und Erwerbstätigkeit (VZAE; SR 142.201) die Fälle der zulässigen Datenbekanntgabe im Bereich des Ausländerrechts "abschliessend". Indem die Vorinstanz § 5 EG ANAG (Kanton Zug) als genügende gesetzliche Grundlage für die erfolgten Meldungen ans Migrationsamt ansehe, habe sie nicht nur kantonales Recht, sondern auch die derogatorische Kraft des Bundesrechts (<ref-law>) verletzt. Verletzt worden seien auch wesentliche Bestimmungen zum Datenschutz (Erfordernis der gesetzlichen Grundlage; § 5 des Datenschutzgesetzes vom 28. September 2000 des Kantons Zug; vgl. für den Bund Art. 17 i.V.m. 19 des Bundesgesetzes über den Datenschutz [DSG]; SR 235.1) und das Recht auf Privatsphäre (<ref-law>).
3.1 Art. 97 Abs. 1 AuG sieht vor, dass sich die direkt mit dem Vollzug des AuG betrauten Behörden gegenseitig in der Erfüllung ihrer Aufgaben unterstützen. Sie erteilen die benötigten Auskünfte und gewähren auf Verlangen Akteneinsicht. Auch die anderen Behörden des Bundes, der Kantone und der Gemeinden sind - im Rahmen der Amtshilfe - verpflichtet, die für den Vollzug des AuG notwendigen Daten und Informationen auf Verlangen den Vollzugsbehörden des AuG bekannt zu geben (Art. 97 Abs. 2 AuG). Entsprechende Auskünfte müssen für den Datenempfänger für die Erfüllung einer gesetzlichen Aufgabe erforderlich sein; systematische Datenbekanntgaben erfordern zudem eine spezifische gesetzliche Grundlage (vgl. CLAUDIA MUND, in: Caroni/Gächter/Thurnherr, Bundesgesetz über die Ausländerinnen und Ausländer [AuG], 2010, N. 8 f. zu Art. 97). Durch Art. 97 Abs. 3 AuG und <ref-law> werden Daten näher bestimmt, für deren Meldung an die Vollzugsbehörden des AuG im Rahmen von Art. 97 Abs. 1 sogar eine gesetzlich umschriebene Meldepflicht besteht; dies betrifft im Allgemeinen die Eröffnung von Strafuntersuchungen, die Änderungen des Zivilstands oder der Bezug von Sozialleistungen.
3.2 Die kantonalen Migrationsämter sind Vollzugsbehörden für das AuG; sie müssen von "anderen Behörden" - etwa der Einwohnerkontrolle der Gemeinden - in Erfüllung ihrer Aufgaben unterstützt werden. Um ihre gesetzlichen Aufgaben zu erfüllen, dürfen die kantonalen Migrationsämter hierfür erforderliche Auskünfte bei den Gemeinden einholen (Art. 97 Abs. 2 AuG). Als einschlägige kantonale Bestimmung hält § 5 Abs. 1 EG ANAG (Kanton Zug) unter dem Titel "Mitteilungspflicht" fest, dass die Gemeinden das Amt für Migration unterstützen und diesem "unverzüglich alle Tatsachen der Einwohnerkontrolle und des Zivilstandsamtes" mitteilen, die ausländische Staatsangehörige betreffen. Wenn die Vorinstanz demnach davon ausgeht, die erforderliche gesetzliche Grundlage für eine systematische Information über die An- und Abmeldungen sei gegeben, verletzt sie entgegen der Ansicht des Beschwerdeführers weder Bundesrecht (Art. 97 AuG, <ref-law>) noch wendet sie das kantonale Recht willkürlich an (§ 5 Abs. 1 EG ANAG [Kanton Zug]; § 5 Abs. 2 lit. a i.V.m. § 8 Datenschutzgesetz vom 28. September 2000 [Kanton Zug]; vgl. auch oben E. 1.4).
Vor diesem Hintergrund geht auch die Rüge des Beschwerdeführers ins Leere, wonach das ANAG grundsätzlich anders konzipiert sei als das AuG und daher das EG (ANAG) des Kantons Zug per se im Widerspruch zu den Bestimmungen des AuG stehe. Das EG (ANAG) des Kantons Zug hat, sofern es nicht gegen Bundesrecht verstösst, eine eigenständige Bedeutung. Sicherlich ist es wünschenswert, dass der Kanton die entsprechende Anpassung der Einführungsgesetze vornimmt; eine Bundesrechtsverletzung (fehlende gesetzliche Grundlage für die Datenerhebung) kann der Beschwerdeführer mit seinen Vorbringen zum Datenschutz aber nicht dartun.
4. Der Beschwerdeführer macht geltend, er habe sich von 2005 bis 2009 hauptsächlich in der Schweiz aufgehalten; sein Lebensmittelpunkt sei in der Schweiz gewesen. Nach Spanien sei er nur gereist, um in der Schweiz nicht zugelassene Medikamente zu kaufen. Seine Niederlassungsbewilligung sei daher nicht wegen Auslandaufenthalts erloschen.
4.1 Der Beschwerdeführer kann sich als spanischer Staatsangehöriger auf das FZA berufen. Der Widerruf bzw. das Erlöschen einer Niederlassungsbewilligung EU/EFTA ist im FZA nicht geregelt; die landesrechtlichen Voraussetzungen zum Erlöschen der Niederlassungsbewilligung dürfen jedoch nicht so ausgestaltet sein, dass sie einen staatsvertraglich gewährleisteten Anspruch auf Aufenthalt vereiteln (vgl. Urteil 2C_831/2010 vom 27. Mai 2011 E. 2.2; 2C_408/2010 vom 15. Dezember 2010 E. 3). Gemäss Art. 5 der Verordnung vom 22. Mai 2002 über die Einführung des freien Personenverkehrs (VEP; SR 142.203) erhalten EU- und EFTA-Angehörige eine unbefristete Niederlassungsbewilligung EU/EFTA gestützt auf Art. 34 AuG und die Art. 60-63 VZAE sowie nach Massgabe der von der Schweiz abgeschlossenen Niederlassungsvereinbarungen (<ref-ruling> E. 4.2 S. 55; <ref-ruling> E. 3.3 S. 258; vgl. auch ZÜND/ARQUINT HILL, in: Uebersax/Rudin/Hugi Yar/Geiser [Hrsg.], Ausländerrecht, 2. Aufl. 2009, Rz. 8.15). Gemäss <ref-law> gilt für den Widerruf der Niederlassungsbewilligung EU/EFTA die Bestimmung von Art. 63 AuG. Die Niederlassungsbewilligung EU/EFTA erlischt gemäss der Bestimmung von Art. 61 Abs. 2 AuG, wenn eine ausländische Person die Schweiz sechs Monate verlässt, ohne sich abzumelden (vgl. auch Art. 6 Abs. 5, Art. 12 Abs. 5 und Art. 24 Abs. 6 Anhang 1 FZA).
Nach der Rechtsprechung und <ref-law> erlischt die Niederlassungsbewilligung wegen Aufenthaltsunterbruchs auch dann, wenn die ausländische Person während eines grösseren Zeitraums landesabwesend ist, jeweils vor Ablauf von sechs Monaten für beschränkte Zeit in die Schweiz zurückkehrt, dies aber bloss zu Geschäfts- oder Besuchszwecken tut. Bei solchen Verhältnissen werden daher nicht etwa die (verschiedenen) Ausreisezeitpunkte, sondern vielmehr die Frage nach dem Lebensmittelpunkt zum ausschlaggebenden Kriterium (vgl. bereits <ref-ruling> E. 2c und d S. 372 f.; Urteil 2C_609/2011 vom 3. April 2012 E. 3.2; 2C_540/2011 vom 19. Dezember 2011 E. 3.2; ZÜND/ARQUINT HILL, a.a.O., Rz. 8.9).
4.2 Entgegen der Ansicht des Beschwerdeführers hat die Vorinstanz den Sachverhalt hinsichtlich seiner Landesabwesenheit von Mitte April 2005 bis Ende 2009 nicht offensichtlich unrichtig erstellt und die Beweismittel auch nicht willkürlich gewürdigt:
4.2.1 Der Beschwerdeführer hätte sämtliche Änderungen betreffend seinen Wohnsitz den zuständigen Behörden melden müssen (Art. 12 Abs. 2 und Art. 15 AuG); ihm oblag im Verfahren vor den Vorinstanzen eine Mitwirkungspflicht (Art. 90 AuG); auch trifft ihn eine Pflicht zur Beweisbeschaffung (vgl. Art. 90 lit. b AuG; vgl. UEBERSAX, a.a.O., Rz. 7.273 f.). Er lebt nach seinen Angaben mehrheitlich in der Schweiz, hat aber selbst eingeräumt, dass er seit 2005 nicht mehr an der der Einwohnerkontrolle gemeldeten Adresse gewohnt hat. Zunächst gab er an, eine unbefristete Kündigung des Mietverhältnisses durch C._ sei hierfür der Grund. Später teilte er den Behörden mit, er halte sich bei unterschiedlichen anderen Personen regelmässig auf, deren Namen er den Behörden zunächst nicht bekannt geben wollte. Ebenso wenig war er bereit, die Rechnungen seiner Telefonanbieter offenzulegen. Vor der Vorinstanz hat der Beschwerdeführer sodann Zeugenaussagen als Beweismittel angeboten, um auf seinen Lebensmittelpunkt in der Schweiz hinzuweisen.
4.2.2 Die durch den Beschwerdeführer eingereichten Erklärungen beinhalten im Wesentlichen Bestätigungen, dass er "immer wieder bei uns übernachtet hat" bzw. "ich ihn öfters gesehen habe". Ihnen ist, wie die Vorinstanz zutreffend ausführt, zwar zu entnehmen, dass die Zeugnis ablegenden Personen den Beschwerdeführer kennen und er sich ab und zu in der Schweiz aufgehalten hat. Die Bestätigungen enthalten jedoch keinerlei Angaben über das Aufenthaltsdatum, die genaue Aufenthaltsdauer und die Häufigkeit der erfolgten Übernachtungen. Um eine dauerhafte Anwesenheit und den Lebensmittelpunkt in der Schweiz für die erforderlichen mindestens viereinhalb Jahre zu bestätigen, sind diese Zeugenaussagen daher ungeeignet. Der Beschwerdeführer hat anlässlich seiner Einvernahme vielmehr bestätigt, dass er nicht an der Adresse wohne, die er gegenüber der zuständigen Einwohnerkontrolle und der zuständigen Ausländerbehörde als seine Wohnadresse angegeben habe. Vor diesem Hintergrund ist es nicht zu beanstanden, wenn das Verwaltungsgericht vom Beschwerdeführer zunächst relativ einfach zu beschaffende minimale Sachbeweise für einen ständigen und nicht nur besuchsweisen Aufenthalt - etwa das Vorlegen von Rechnungskopien seiner Telefongesellschaften - verlangt und damit voraussetzt, dass sein Standpunkt einigermassen glaubhaft erscheint, bevor weitere (weniger aussagekräftige) Urkundenbeweise berücksichtigt werden (vgl. Urteil 2C_81/2011 vom 1. September 2011 E. 3.7).
Der Beschwerdeführer macht zwar geltend, er lebe heute bei Frau D._, unterlässt es jedoch, seine Behauptung in Auseinandersetzung mit dem eingereichten Entscheid zu substanziieren (vgl. E. 1.5). Dies, wie auch die eingereichten Bestätigungen der Gemeinde, wonach der Beschwerdeführer Sozialhilfe beziehe, oder Bestätigungen des Hausarztes für einzelne ambulante Konsultationen, u.a. für das nicht mehr relevante Jahr 2010, vermögen weder für sich allein noch in ihrer Gesamtheit einen Lebensmittelpunkt in der Schweiz glaubhaft zu machen. Es liegen keine Belege vor, die es den Behörden erlauben würden nachzuvollziehen, wie der Beschwerdeführer ohne eigene Wohnung, ohne Arbeit und von der Sozialhilfe lebend viereinhalb Jahre in der Schweiz verbracht haben soll.
4.3 Die Annahme der Vorinstanz, der Beschwerdeführer sei für die Zeitspanne vom 17. April 2005 bis Ende 2009 nur vorübergehend für ein paar Tage und zu Besuchszwecken in die Schweiz zurückgekehrt bzw. habe seinen Lebensmittelpunkt ins Ausland verlegt, kann somit nicht als einseitig oder gar willkürlich gelten. Das Bundesgericht ist demnach an die Sachverhaltsfeststellung der Vorinstanz gebunden (vgl. <ref-law>). Auch die Beweise wurden auf korrekte Weise gewürdigt, sodass insgesamt von einer langjährigen Landesabwesenheit unter Verlagerung des Lebensmittelpunkts ins Ausland auszugehen ist. Die Vorinstanz hat zu Recht angenommen, die Niederlassungsbewilligung des Beschwerdeführers sei infolge längeren Auslandaufenthalts erloschen, da dieser länger als sechs Monate landesabwesend war (Art. 60 Abs. 2 AuG i.V.m. <ref-law>; Art. 6 Abs. 5 Anhang 1 FZA).
4.4 Unter diesen Voraussetzungen kann sich der Beschwerdeführer auch nicht auf ein Verbleiberecht gestützt auf das FZA berufen (Art. 4 Abs. 2 Anhang 1 FZA i.V.m. Art. 16 Abs. 1 FZA; Eventualantrag): Die Verordnung Nr. 1251/70 (EWG; ABl. 1970 Nr. L 142, S. 24 ff.), auf welche Art. 4 Abs. 2 Anhang I des FZA statisch verweist (vgl. hierzu Urteil 2C_688/2011 vom 21. Februar 2012 E. 2.4; vgl. für die EU mittlerweile Art. 17 der Richtlinie 2004/38/EG des Europäischen Parlaments und des Rates vom 29. April 2004 über das Recht der Unionsbürger und ihrer Familienangehörigen, sich im Hoheitsgebiet der Mitgliedstaaten frei zu bewegen und aufzuhalten; ABl. 2004 Nr. L 158, S. 123 ff.), verleiht einem Arbeitnehmenden u.a. dann ein Verbleiberecht, wenn er infolge dauernder Arbeitsunfähigkeit eine Beschäftigung aufgibt, nachdem er sich seit mindestens zwei Jahren im Hoheitsgebiet des Vertragsstaates ständig aufgehalten hat (Art. 2 Abs. 1 lit. b der Verordnung Nr. 1251/70 [EWG]). Ob der Beschwerdeführer die in Art. 2 der Verordnung Nr. 1251/70 (EWG) aufgezählten Voraussetzungen tatsächlich erfüllt, kann dahingestellt bleiben, da entsprechende Ansprüche ohnehin nur durch Aufenthaltsunterbrechungen unberührt bleiben, die sechs aufeinanderfolgende Monate nicht überschreiten (Art. 6 Abs. 2 der Verordnung Nr. 1251/70 [EWG]). Ein Verbleiberecht nach FZA kann mit anderen Worten dem Erlöschen der Niederlassungsbewilligung infolge längerer Landesabwesenheit nicht entgegenstehen. Der Beschwerdeführer macht auch nicht geltend, zwecks Arbeit oder Stellensuche erneut in die Schweiz eingereist zu sein (Art. 2 i.V.m. Art. 6 Anhang I FZA; Art. 2 Abs. 2 S. 2 Anhang I FZA). Dass er mittlerweile über ausreichend Existenzmittel verfügte, um sich als Nichterwerbstätiger in der Schweiz aufhalten zu können (Art. 24 Anhang 1 FZA), bringt er nicht vor. Eine Rückweisung an die Vorinstanz erübrigt sich.
5. Die Beschwerde ist somit unbegründet und abzuweisen, soweit darauf einzutreten ist. Da sich die Beschwerde nicht als aussichtslos erweist und der Beschwerdeführer bedürftig ist, kann die beantragte unentgeltliche Rechtspflege bewilligt und auf die Erhebung von Gerichtskosten verzichtet werden (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen.
2.1 Es werden keine Kosten erhoben.
2.2 Dem Beschwerdeführer wird Rechtsanwalt Florian Wick als Rechtsbeistand beigegeben. Diesem wird aus der Gerichtskasse eine Entschädigung von Fr. 3'000.-- ausgerichtet.
3. Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zug, Verwaltungsrechtliche Kammer, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 18. Januar 2013
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Die Gerichtsschreiberin: Hänni