Sachverhalt:
A. Der kroatische Staatsangehörige X._ (geb. 1956) reiste im März 1987 zusammen mit seiner Ehefrau (geb. 1958) und ihrem gemeinsamen Sohn Y._ (geb. 1982) in die Schweiz ein. Sie erhielten Aufenthaltsbewilligungen und im Jahr 1997 Niederlassungsbewilligungen. Im Jahr 1987 wurde ihre Tochter Z._ in der Schweiz geboren.
Vom 14. Juni 2007 bis zum 3. Juli 2008 befand sich X._ in Deutschland in Untersuchungshaft. Am 29. November 2007 verurteilte ihn das dortige Amtsgericht Traunstein wegen Geldfälschung zu einer Freiheitsstrafe von zwei Jahren und drei Monaten. Auf Berufung hin reduzierte das Landgericht Traunstein mit Urteil vom 3. Juli 2008 die Strafe auf zwei Jahre, die zur Bewährung ausgesetzt wurde. Noch im selben Monat kehrte X._ in die Schweiz zurück und ersuchte beim Departement des Innern des Kantons Solothurn um "Wiederzulassung". Der Antrag wurde mit Schreiben vom 6. Oktober 2008 abgelehnt und X._ eine Frist zur Ausreise gesetzt. Gleichzeitig wurde er darauf hingewiesen, dass er eine kostenpflichtige anfechtbare Verfügung verlangen könne. Am 23. Oktober 2008 stellte er ein solches Gesuch. Darauf erlaubte ihm das kantonale Departement, den Ausgang des Verfahrens in der Schweiz abzuwarten. Am 23. Dezember 2010 erliess das Departement schliesslich die anfechtbare Verfügung, mit welcher es das Gesuch um "Wiederzulassung" erneut ablehnte. Die dagegen beim Verwaltungsgericht des Kantons Solothurn erhobene Beschwerde wurde am 21. Juni 2011 abgewiesen.
B. Mit Beschwerde vom 28. Juli 2011 beantragt X._ dem Bundesgericht, das Urteil des Verwaltungsgerichts vom 21. Juni 2011 aufzuheben und seinen Aufenthalt "in Anerkennung eines Härtefalls im Sinne von Art. 30 Abs. 1 lit. b AuG neu zu regeln und eine Niederlassungs- oder Aufenthaltsbewilligung zu erteilen". Eventualiter sei die Angelegenheit zur Neubeurteilung an die Vorinstanz zurückzuweisen. Ausserdem ersucht er um Gewährung der aufschiebenden Wirkung und unentgeltlichen Rechtspflege.
Das kantonale Departement des Innern - vertreten durch das kantonale Amt Migration und Schweizer Ausweise - sowie das Verwaltungsgericht stellen ohne weitere Ausführungen den Antrag, die Beschwerde abzuweisen, soweit darauf eingetreten werden könne. Das Bundesamt für Migration beantragt Abweisung der Beschwerde. Innert der bis zum 14. November 2011 angesetzten Frist hat sich X._ nicht mehr geäussert.
C. Der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts hat der Beschwerde mit Verfügung vom 3. August 2011 hinsichtlich der Ausreiseverpflichtung antragsgemäss die aufschiebende Wirkung zuerkannt

Erwägungen:
1. Gemäss <ref-law> ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten auf dem Gebiet des Ausländerrechts unzulässig betreffend Bewilligungen, auf die kein Anspruch besteht (Ziff. 2), und wenn es um Abweichungen von den Zulassungsvoraussetzungen geht (Ziff. 5).
1.1 Die Vorinstanzen gehen davon aus, dass die dem Beschwerdeführer ursprünglich erteilte Niederlassungsbewilligung während der Untersuchungshaft in Deutschland von Juni 2007 bis Juli 2008 erloschen sei, da dieser sich insoweit ohne Unterbruch länger als sechs Monate im Ausland aufgehalten hat. Das entspricht sowohl dem im Jahr 2007 noch anwendbaren Art. 9 Abs. 3 lit. c des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; BS 1 121, in der Fassung vom 8. Oktober 1948, AS 1949 I 221 227) als auch dem seit dem 1. Januar 2008 geltenden Art. 61 Abs. 2 AuG (SR 142.20). Keine Rolle spielt, dass der längere Auslandsaufenthalt aufgrund der Haft unfreiwillig war (vgl. zum ANAG: <ref-ruling> E. 2c S. 372; speziell zur Haft: Urteil des Bundesgerichts 2A.308/2001 vom 15. November 2001 E. 3 mit Hinweisen; zum AuG: Urteil des Bundesgerichts 2C_853/2010 vom 22. März 2011 E. 5.1). Insoweit räumt auch der Beschwerdeführer ein, dass seine Niederlassungsbewilligung während der Haft erloschen sei. Er macht aber geltend, die Verweigerung der Bewilligung seines erneuten Aufenthaltes in der Schweiz verletze sein Recht auf Achtung des Familienlebens nach Art. 8 EMRK.
1.2 Da die Ehefrau des Beschwerdeführers über eine Niederlassungsbewilligung in der Schweiz verfügt, kann sich der Beschwerdeführer tatsächlich auf einen aus Art. 8 EMRK abgeleiteten Anspruch auf Anwesenheit im Sinne von <ref-law> berufen (vgl. <ref-ruling> E. 1.3.1 S. 145). Zudem kommt hier ein Bewilligungsanspruch nach Art. 43 Abs. 1 AuG in Betracht. Denn dieser Bestimmung zufolge haben ausländische Ehegatten von Personen mit Niederlassungsbewilligung Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, wenn sie mit diesen zusammenwohnen. Der Beschwerdeführer beabsichtigt, mit seiner Ehefrau zusammenzuleben. Da das Bundesgericht das Recht von Amtes wegen anwendet (vgl. <ref-law>), spielt keine Rolle, dass der Beschwerdeführer diese Bestimmung nicht ausdrücklich erwähnt. Im Übrigen hat das auch die Vorinstanz nicht getan.
In diesem Umfang ist die Beschwerde gemäss <ref-law> zulässig. Ob die Bewilligung wirklich zu erteilen ist oder ob Erlöschensgründe dem entgegenstehen (vgl. Art. 51 AuG), ist erst im Rahmen der Begründetheit der Beschwerde zu prüfen. Soweit der Beschwerdeführer die sofortige Wiedererteilung einer Niederlassungsbewilligung anstrebt, ist auf seine Beschwerde indes nicht einzutreten. Einen solchen Anspruch hat er gemäss Art. 43 Abs. 2 AuG erst nach einem ordnungsgemässen und ununterbrochenen Aufenthalt von fünf Jahren. Wie in Erwägung 1.1 gesehen, fehlt es zum Vornherein an dieser Bedingung, da - wie der Beschwerdeführer auch einräumt - er seine frühere Bewilligung wegen des Auslandsaufenthaltes verloren hatte und er sich seither erst ab Juli 2008, somit seit weniger als fünf Jahren wieder in der Schweiz aufhält.
Soweit der Beschwerdeführer unabhängig von Art. 8 EMRK die Wiederzulassung gemäss Art. 30 Abs. 1 lit. k AuG und Art. 49-51 der Verordnung vom 24. Oktober 2007 über Zulassung, Aufenthalt und Erwerbstätigkeit (VZAE; SR 142.201) oder einen Härtefall gemäss Art. 30 Abs. 1 lit. b AuG geltend machen sollte, besteht kein Anspruch auf eine Bewilligung im Sinne von <ref-law>, weshalb auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten nicht einzutreten wäre (vgl. auch <ref-law>; Urteil des Bundesgerichts 2C_75/2011 vom 6. April 2011 E. 1.1). Zwar erhebt der Beschwerdeführer hilfsweise die subsidiäre Verfassungsbeschwerde nach <ref-law>. Es fehlt insoweit jedoch an geeigneten und hinreichend begründeten Rügen (vgl. Art. 116 i.V.m. Art. 42 Abs. 2 und 106 Abs. 2 BGG; <ref-ruling>; Urteil des Bundesgerichts 2C_830/2010 vom 10. Juni 2011 E. 1.2).
2. 2.1 Der Bewilligungsanspruch nach Art. 43 Abs. 1 AuG erlischt gemäss Art. 51 Abs. 2 AuG, wenn er rechtsmissbräuchlich geltend gemacht wird (lit. a) oder Widerrufsgründe nach Art. 62 AuG vorliegen (lit. b). Mit Blick auf die von den Vorinstanzen geltend gemachten Umstände, insbesondere die strafrechtliche Verurteilung des Beschwerdeführers in Deutschland, fragt sich, ob hier der Widerrufsgrund nach Art. 62 AuG der (Wieder-)Erteilung einer Aufenthaltsbewilligung entgegensteht.
2.2 Gemäss Art. 62 AuG kann eine Bewilligung widerrufen werden, wenn der Ausländer zu einer längerfristigen Freiheitsstrafe verurteilt wurde (lit. b) oder wenn er erheblich oder wiederholt gegen die öffentliche Sicherheit und Ordnung in der Schweiz oder im Ausland verstossen hat oder diese gefährdet oder die innere oder die äussere Sicherheit gefährdet (lit. c). Vorliegend ist der erstgenannte Widerrufsgrund auf jeden Fall erfüllt, da der Beschwerdeführer zu zwei Jahren Freiheitsstrafe verurteilt wurde. Unerheblich ist dabei, dass sowohl der Tatort als auch das verurteilende Gericht im Ausland liegen. Das Gleiche gilt für den Umstand, dass der Vollzug der Strafe zur Bewährung ausgesetzt wurde (vgl. <ref-ruling> E. 4.2 S. 379 ff.; Urteil des Bundesgerichts 2C_515/2009 vom 27. Januar 2010 E. 2.1). Diese Umstände spielen allenfalls im Rahmen der Interessenabwägung eine Rolle.
2.3 Wie soeben angedeutet, rechtfertigt das Vorliegen eines Widerrufsgrundes die Bewilligungsverweigerung allein noch nicht. Diese muss auch verhältnismässig sein (vgl. <ref-ruling> E. 4.3 S. 381 f.). Eine vergleichbare Interessenabwägung wird ebenso von Art. 8 Ziff. 2 EMRK für einen Eingriff in das Recht auf Achtung des Familienlebens vorausgesetzt (vgl. <ref-ruling> E. 4.3 S. 381 f.; <ref-ruling> E. 2 S. 5 f. mit Hinweisen). Hierbei interessiert namentlich, ob den nahen Familienangehörigen zugemutet werden kann, dem Ausländer, der keine Bewilligung erhält, ins Ausland zu folgen. Eine allfällige Unzumutbarkeit der Ausreise führt aber nicht für sich allein zur Unzulässigkeit einer Bewilligungsverweigerung (vgl. <ref-ruling> E. 4b S. 131).
2.4 Der Beschwerdeführer beanstandet, dass die Interessenabwägung der Vorinstanz "zu kurz" greife. Sie beachte nur einen Bruchteil der vom Europäischen Gerichtshof für Menschenrechte namentlich im Urteil Boultif gegen Schweiz vom 2. August 2001 (in: Recueil CourEDH 2001-IX S. 137 und VPB 65/2001 Nr. 138 S. 1392) aufgestellten Kriterien und gewichte diese zudem falsch. Insbesondere die Situation seiner Ehefrau berücksichtige sie nicht hinreichend. Das Gleiche gelte für den Umstand, dass ihm das Landgericht Traunstein im Strafurteil eine günstige Sozialprognose gestellt habe.
2.5 Das Departement des Innern hatte in seiner Verfügung vom 23. September 2010 in Bezug auf Art. 43, 51 und 62 AuG überhaupt keine Verhältnismässigkeitsprüfung vorgenommen, sondern allein darauf abgestellt, dass die Widerrufsgründe der Art. 62 lit. b und c AuG erfüllt seien. Die Vorinstanz nimmt hingegen eine Interessenabwägung vor. Sie hält insoweit namentlich fest, der Beschwerdeführer habe in der Schweiz eine intakte Familie. Die Ehefrau sei indessen ebenfalls kroatische Staatsangehörige und vor rund 24 Jahren gemeinsam mit dem Beschwerdeführer eingereist. Das Eheleben könne folglich auch in der Heimat fortgeführt werden. Dass die wirtschaftlichen Aussichten dort nicht sehr günstig sein mögen, sei für sich allein nicht ausschlaggebend. Seine beiden erwachsenen und wirtschaftlich selbständigen Kinder könnten ihrem Vater in die Heimat folgen. Oder der Beschwerdeführer könne sie auch in der Schweiz im Rahmen von Touristenaufenthalten besuchen. Hinsichtlich der (letzten) Straftat, die der Verurteilung in Deutschland zugrunde lag, sei schon eine "gewisse" Zeit verstrichen. Der Beschwerdeführer verhalte sich nun wohl. Es sei aber nicht auszuschliessen, dass er in Zukunft wieder Straftaten begehe.
2.6 Der Beschwerdeführer bemerkt zu Recht, dass sich die Vorinstanz mit keinem Wort mit der - wenn auch knapp - begründeten Einschätzung des Landgerichts, die zur Aussetzung zur Bewährung des Vollzugs der Freiheitsstrafe geführt hatte, befasst. Die deutschen Gerichte erwähnten namentlich die Einsicht, Reue und Haftempfindlichkeit des Beschwerdeführers. Letztmals war der Beschwerdeführer im September 2006 deliktisch tätig, indem er sich gefälschte Banknoten in Höhe von 100'000.-- Dollar besorgte, um sie als echt in Verkehr zu bringen. Hiefür wurde er zur zweijährigen Freiheitsstrafe, die zur Bewährung ausgesetzt wurde, verurteilt. Zuvor war er in der Schweiz im Jahr 2001 wegen grober Verletzung der Verkehrsregeln mit Fr. 800.-- gebüsst worden. Im Jahr 2005 wurde er wegen pflichtwidrigen Verhaltens bei einem Unfall sowie grober Verletzung von Verkehrsregeln mit einer Busse von Fr. 2'000.-- belegt. Die Wiederholung von Delikten mit zudem steigender Intensität spricht eher für eine Wiederholungsgefahr. Allerdings hat der Beschwerdeführer seit Herbst 2006 bzw. seit seiner Freilassung aus der Untersuchungshaft, die von Juni 2007 bis Juli 2008 dauerte, sich keine Straftaten mehr zuschulden kommen lassen. Immerhin waren seit der letzten Tat knapp fünf Jahre vergangen, als die Vorinstanz entschied. In diesem Zeitpunkt war die Wiederholungsgefahr im Sinne des Landgerichts Traunstein eher gering. Auch wenn die begangenen Delikte nicht zu verharmlosen sind, gab es zudem keine Personenschäden. Wohl hat der Beschwerdeführer gemäss Betreibungsregisterauszug mit rund Fr. 140'000.-- hohe Schulden; auch seine Ehefrau hat offene Verlustscheine über Fr. 70'000.--. Das könnte wieder zur Straffälligkeit verleiten. Obwohl der Beschwerdeführer seit seiner Rückkehr in die Schweiz - trotz Ersuchen und der Vorlage entsprechender Arbeitsangebote - nicht arbeiten durfte, beging er aber keine Delikte mehr. Das kantonale Verfahren, währenddem der Beschwerdeführer in der Schweiz verweilen durfte, dauerte zudem fast drei Jahre, ohne dass Letzterer hiefür verantwortlich ist. Bei einer reell anzunehmenden Rückfallgefahr hätten die Behörden - hier vor allem das kantonale Departement - kaum dermassen lange zugewartet bzw. zuwarten dürfen (vgl. Urteil des Bundesgerichts 2C_454/2011 vom 24. November 2011 E. 2.5 und 2.6).
Die Schulden fielen sodann nicht wegen einer liederlichen Lebensführung an. Sie entstanden vielmehr ab dem Jahr 2000 im Zusammenhang mit der selbständigen Geschäftstätigkeit des Beschwerdeführers, welche dieser nach seiner professionellen Sportler- und Trainertätigkeit und einer Beschäftigung als Metzger aufgenommen hatte. Die Eheleute haben während ihres langjährigen Aufenthaltes in der Schweiz keine Sozialhilfe bezogen.
Die Vorinstanz berücksichtigt auch nicht hinreichend, dass der Beschwerdeführer in der Schweiz an Diabetes mit Sehstörungen erkrankt ist. Trotz entsprechendem Vorbringen beachtet sie überhaupt nicht, dass seine Ehefrau seit längerem IV-Rentnerin ist, gesundheitlich sehr angeschlagen ist und vor allem psychisch auf die Unterstützung durch ihren Ehegatten angewiesen ist. Als die Vorinstanz ihr Urteil fällte, lebte die Ehefrau seit über 24 Jahren in der Schweiz, wo sich auch ihre Kinder aufhalten und aufgewachsen sind. Diese sind zwar volljährig, pflegen aber noch regelmässig Kontakte zu ihren Eltern und tragen insoweit zum Wohlbefinden der gesundheitlich beeinträchtigen Ehefrau und Mutter bei. Schliesslich äussert sich die Vorinstanz nicht zur Absicht des Beschwerdeführers, durch Arbeitsaufnahme für sich und seine Ehefrau, die eine bescheidene IV-Rente und Ergänzungsleistungen bezieht, aufzukommen und seine Schulden allmählich zurückzuzahlen. Auch insoweit besteht ein Interesse an seinem Verbleib in der Schweiz.
2.7 Auch wenn es sich vorliegend um einen Grenzfall handelt, erweist es sich aufgrund vorstehender Darlegungen als unverhältnismässig, dem Beschwerdeführer eine - zunächst auf ein Jahr befristete - Aufenthaltsbewilligung zu verweigern. Allerdings ist der Beschwerdeführer gemäss Art. 96 Abs. 2 AuG zu verwarnen. Sollte er wieder deliktisch oder sonst wie nachteilig auffallen oder entgegen seinen Ankündigungen nicht ernsthaft dafür sorgen, dass die Schuldenlast abgebaut wird, würde er sein Aufenthaltsrecht und damit die Aufrechterhaltung bzw. die künftige Verlängerung seiner Bewilligung verwirken. Ebenso ist sein weiterer Aufenthalt an die Bedingung zu knüpfen, dass er mit seiner Ehefrau zusammenlebt und ihr die nötige sowie zumutbare Unterstützung gewährt. Insoweit kann offen bleiben, ob die zusätzlichen, weiter führenden Vorbringen und Belege zum Gesundheitszustand der Ehefrau, die erstmals vor Bundesgericht geltend gemacht werden, überhaupt berücksichtigt werden können. Immerhin sei bemerkt, dass sich die Vorinstanz nicht zu dem bei ihr gestellten Antrag auf Beiziehung der IV-Akten der Ehefrau geäussert hat (vgl. <ref-law>; <ref-ruling> E. 1.5 S. 146 f.).
3. Diesem Ausgang entsprechend hat der Kanton Solothurn dem Beschwerdeführer eine leicht reduzierte Parteientschädigung auszurichten (vgl. Art. 68 Abs. 1-3 BGG). Gerichtskosten werden - auch mit Blick auf die Einkommens- und Vermögensverhältnisse des Beschwerdeführers und seiner Ehefrau - nicht erhoben (vgl. Art. 65 f. BGG). Über die Kosten und Parteientschädigungen im kantonalen Verfahren wird die Vorinstanz neu zu befinden haben (vgl. Art. 67 und 68 Abs. 5 BGG). Das Gesuch um unentgeltliche Rechtspflege wird - soweit nicht gegenstandslos geworden - bezüglich einer weiter gehenden Entschädigung der Anwältin abgewiesen. Denn soweit die Beschwerde nicht gutgeheissen wurde bzw. auf sie nicht einzutreten war, erwies sie sich gemäss <ref-law> als aussichtslos.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird im Sinne der Erwägungen teilweise gutgeheissen, soweit darauf einzutreten ist, und das Urteil des Verwaltungsgerichts des Kantons Solothurn vom 21. Juni 2011 aufgehoben.
1.1 Dem Beschwerdeführer ist eine Aufenthaltsbewilligung zu erteilen.
1.2 Der Beschwerdeführer wird im Sinne der Erwägungen nach Art. 96 Abs. 2 AuG verwarnt.
1.3 Die Sache wird an das Verwaltungsgericht des Kantons Solothurn zu neuem Entscheid über die Verfahrenskosten und Parteientschädigungen im kantonalen Verfahren zurückgewiesen.
2. Auf die subsidiäre Verfassungsbeschwerde wird nicht eingetreten.
3. Es werden keine Gerichtskosten erhoben.
4. Der Kanton Solothurn hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 1'500.-- zu entschädigen.
5. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen, soweit dieses nicht gegenstandslos geworden ist.
6. Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Solothurn und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 3. April 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Küng