Sachverhalt:
A. Die deutsche Staatsangehörige Y._ (geb. 1982) reiste im Februar 2008 zwecks Arbeitsaufnahme in die Schweiz ein. Sie erhielt eine Aufenthaltsbewilligung EG/EFTA. Nach einem kurzen Aufenthalt im Kanton Graubünden verlegte sie im März 2008 ihren Wohnsitz in den Kanton Basel-Landschaft. Am 14. April 2008 heiratete sie im Kosovo den von dort stammenden X._ (geb. 1980). Aus der Beziehung, die bereits einige Jahre zuvor bestand, stammt die Tochter T._ (geb. 2005). Im Januar 2009 ist eine zweite gemeinsame Tochter, U._, geboren.
Auf Antrag der Ehefrau bewilligten die Behörden im August 2008 die Einreise von X._. Dieser gab anschliessend in seiner Anmeldung an, nicht vorbestraft zu sein. Ermittlungen ergaben indes, dass X._ zwischen 1999 und 2007 in Deutschland mehrfach wegen diverser Straftaten verurteilt worden war, und zwar am:
- 20. Januar 1999 vom Amtsgericht Warburg: Verwarnung und Jugendarrest von vier Wochen wegen versuchten Diebstahls und wegen gemeinschaftlichen Diebstahls oder Hehlerei;
- 28. November 1999 vom Amtsgericht Bad Arolson: Jugendarrest von zwei Wochen und 60 Stunden Arbeitsleistung wegen Urkundenfälschung sowie wegen unerlaubten Erwerbs von Betäubungsmitteln (Heroin) in 97 Fällen und wegen Beihilfe zu gewerbsmässigem Handeltreiben mit Betäubungsmitteln;
- 14. Mai 2001 vom Amtsgericht Baden-Baden: Geldstrafe von 20 Tagessätzen wegen Körperverletzung;
- 10. Dezember 2001 vom Amtsgericht Baden-Baden: Geldstrafe von 20 Tagessätzen wegen Fahrens ohne Fahrerlaubnis;
- 5. März 2002 vom Amtsgericht Baden-Baden: Geldstrafe von 30 Tagessätzen wegen Körperverletzung und Fahrens ohne Fahrerlaubnis;
- 5. Juni 2002 vom Amtsgericht Kassel: Jugendstrafe von einem Jahr und acht Monaten - unter Einbezug der Verurteilung vom 28. November 1999 - wegen gewerbsmässigen Handeltreibens mit Betäubungsmitteln in 26 Fällen davon in drei Fällen mit nicht geringen Mengen;
- 1. November 2004 vom Amtsgericht Kassel: Geldstrafe von 80 Tagessätzen wegen in Tateinheit begangenen vorsätzlichen Fahrens ohne Fahrerlaubnis, Führens eines nicht haftpflichtversicherten Personenwagens sowie Urkundenfälschung;
- 21. Dezember 2004 vom Amtsgericht Kassel: Geldstrafe von 50 Tagessätzen wegen Diebstahls. Die beiden zuletzt genannten Verurteilungen wurden mit Beschluss vom 31. März 2005 durch Gesamtstrafenbildung in eine Geldstrafe von 100 Tagessätzen umgewandelt;
- 22. Dezember 2004 vom Amtsgericht Karlsruhe: Freiheitsstrafe von acht Monaten wegen Diebstahls;
- 28. Januar 2005 vom Amtsgericht Kassel: Geldstrafe von 30 Tagessätzen wegen unerlaubten Führens einer Schusswaffe und von Munition;
- 4. Juli 2005 vom Amtsgericht Kassel: Freiheitsstrafe von drei Monaten wegen Diebstahls. Am 29. Dezember 2005 wurde zusammen mit der Verurteilung vom 22. Dezember 2004 eine Gesamtstrafe von neun Monaten und zwei Wochen Freiheitsstrafe gebildet;
- 23. September 2005 vom Amtsgericht Baden-Baden: Geldstrafe von 60 Tagessätzen wegen Strassenverkehrsgefährdung in Tateinheit mit Fahren ohne Fahrerlaubnis;
- 8. November 2005 vom Amtsgericht Offenburg: Geldstrafe von 25 Tagessätzen wegen unerlaubtem Besitz von Betäubungsmitteln;
- 18. November 2005 Amtsgericht Baden-Baden: Geldstrafe von 45 Tagessätzen wegen Fahrens ohne Fahrerlaubnis. Die drei zuletzt genannten Verurteilungen wurden mit Beschluss vom 25. April 2006 durch Gesamtstrafenbildung in eine Geldstrafe von 120 Tagessätzen umgewandelt;
- 12. Dezember 2005 vom Amtsgericht Baden-Baden: Geldstrafe von 50 Tagessätzen wegen Fahrens ohne Fahrerlaubnis;
- 15. Mai 2006 vom Amtsgericht Baden-Baden: Geldstrafe von 30 Tagessätzen wegen Beleidigung;
- 17. Juli 2007 vom Amtsgericht Rastatt: Freiheitsstrafe von zwei Monaten wegen Fahrens ohne Fahrerlaubnis;
Zudem liefen dort gegen ihn im Jahr 2008 noch mindestens drei Fahndungen wegen Strafvollstreckung bzw. Strafverfolgung. Ausserdem hatte ihn das Regierungspräsidium Karlsruhe am 3. Dezember 2002 wegen seiner Straffälligkeit aus Deutschland ausgewiesen. Deshalb verweigerte ihm das Amt für Migration des Kantons Basel-Landschaft mit Verfügung vom 6. Januar 2009 die Erteilung einer Aufenthaltsbewilligung und ordnete seine Ausreise an. Die dagegen im Kanton erhobenen Rechtsmittel wurden vom Regierungsrat am 10. März 2009 und anschliessend vom Kantonsgericht am 21. Oktober 2009 abgewiesen.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 28. Januar 2010 beantragt X._ dem Bundesgericht, das Urteil des Kantonsgerichts aufzuheben und die Behörden anzuweisen, ihm eine Aufenthaltsbewilligung zu erteilen. Eventualiter sei das Verfahren zur Vornahme weiterer Abklärungen an das kantonale Amt für Migration zurückzuweisen.
Der Regierungsrat sowie das Bundesamt für Migration stellen den Antrag, die Beschwerde abzuweisen. Das Kantonsgericht hat auf eine Vernehmlassung verzichtet. Das kantonale Amt für Migration hat sich nicht geäussert. Am 3. Juni 2010 hat sich der Regierungsrat ergänzend geäussert.
C. Der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts hat der Beschwerde hinsichtlich der mit dem angefochtenen Urteil verbundenen Ausreiseverpflichtung am 2. Februar 2010 antragsgemäss die aufschiebende Wirkung zuerkannt.

Erwägungen:
1. Gemäss Art. 83 lit. c Ziff. 2 BGG ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten ausgeschlossen auf dem Gebiet des Ausländerrechts betreffend Bewilligungen, auf die weder das Bundes- noch das Völkerrecht einen Anspruch einräumen. Zwar kann der Beschwerdeführer keinen Rechtsanspruch auf eine Aufenthaltsbewilligung unmittelbar aus dem Bundesgesetz vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20) ableiten, da seine Ehefrau nur über eine Aufenthaltsbewilligung in der Schweiz verfügt (vgl. Art. 43 und 44 AuG). Er kann aber wegen seiner Ehe mit der im Inland wohnhaften deutschen Bürgerin grundsätzlich einen Aufenthaltsanspruch gestützt 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 (Freizügigkeitsabkommen, FZA; SR 0.142.112.681) geltend machen. Insoweit greift der erwähnte Ausschlussgrund nicht (vgl. <ref-ruling> E. 1.1 und 1.2 S. 389 ff.; <ref-ruling> E. 1.2 S. 343 f.; BGE 2C_490/2009 vom 2. Februar 2010 E. 1.1).
2. Die Eingabe des Regierungsrates vom 3. Juni 2010 ist aus dem Recht zu weisen, da zum einen die ihm gesetzte Vernehmlassungsfrist bereits abgelaufen war und kein zweiter Schriftenwechsel angeordnet wurde (vgl. Art. 102 BGG) und es sich zum anderen beim Vorbringen und den Beilagen um echte Noven handelt (vgl. <ref-ruling> E. 2.1 S. 344 f.).
3. 3.1 Die Vorinstanzen hatten noch unter Hinweis auf die frühere Praxis des Bundesgerichts (begründet mit <ref-ruling> E. 3.6 S. 9 ff.) eine Anrufung der Nachzugsbestimmungen des Freizügigkeitsabkommens abgelehnt, weil der Beschwerdeführer als Angehöriger eines Nichtvertragsstaats wegen der von Deutschland verfügten Ausweisung nicht mehr über einen Aufenthaltstitel in einem FZA-Vertragsstaat oder EFTA-Staat verfügte (sog. Akrich-Praxis). Inzwischen hat das Bundesgericht auf eine Rechtsprechungsänderung des Gerichtshofes der Europäischen Gemeinschaften (EuGH) hin seine Praxis aber entsprechend angepasst. Demnach werden die Nachzugsregelungen des Abkommens nunmehr ohne Unterscheidung auf alle in Art. 3 Abs. 2 des Anhangs I FZA genannten Familienangehörigen angewendet (sog. Metock-Praxis; vgl. <ref-ruling> E. 3 S. 11 ff.; bestätigt im erwähnten BGE 2C_490/2009 E. 1.1). Diese neue Rechtsprechung findet vorliegend Anwendung, zumal das Bundesgericht gemäss Art. 106 Abs. 1 BGG das Recht von Amtes wegen anwendet. Das Bundesgericht ist im Übrigen weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen und es kann eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen (<ref-ruling> E. 4.3.4 S. 241; <ref-ruling> E. 1.2 S. 252).
3.2 Nach Art. 3 Abs. 1 und 2 lit. a Anhang I FZA hat namentlich der Ehegatte einer Person, die Staatsangehörige einer Vertragspartei ist und ein Aufenthaltsrecht hat, das Recht, bei ihr Wohnung zu nehmen. Die Ehefrau verfügt als Deutsche zwar über eine Aufenthaltsbewilligung EG/EFTA. Aus den Feststellungen der Vorinstanz und den Akten ergibt sich allerdings nicht, ob sie in der Schweiz immer noch erwerbstätig ist. Immerhin hat die Familie zwischen November 2008 und Oktober 2009 Sozialhilfe bezogen. Insoweit könnte die Ehefrau ihres ursprünglichen Aufenthaltsrechts nach dem Freizügigkeitsabkommen verlustig gegangen sein und daraus auch keine Rechte auf Familiennachzug mehr ableiten, weil sie unter keine der im Abkommen vorgesehenen Personenkategorien mehr fällt (vgl. insb. Art. 4 und 6 FZA in Verbindung mit Art. 6 ff. Anhang I FZA). Wie es sich damit verhält, kann hier, wo es nur um den Nachzug des Ehemannes geht, aber aus nachfolgenden Erwägungen offen gelassen werden.
3.3 Die durch das Abkommen eingeräumten Rechte dürfen nur durch Massnahmen, die aus Gründen der öffentlichen Ordnung, Sicherheit und Gesundheit gerechtfertigt sind, eingeschränkt werden. Zudem ist die gemeinschaftsrechtliche Richtlinie 64/221/EWG zu beachten (vgl. Art. 5 Anhang I FZA). Nach der an die Praxis des EuGH angeglichenen Rechtsprechung des Bundesgerichts kommt es bei Art. 5 Anhang I FZA - neben der auch nach nationalem Recht vorzunehmenden Interessenabwägung - wesentlich auf das Risiko an, dass der Ausländer wieder Delikte begeht. Es muss insoweit eine gegenwärtige und hinreichend schwere Gefährdung, die Grundinteressen der Gesellschaft berührt, von der betroffenen Person ausgehen, damit ihr der Aufenthalt verweigert werden darf. Demgegenüber stellt das Rückfallrisiko im nationalen Ausländerrecht grundsätzlich nur einen Aspekt der vorzunehmenden Interessenabwägung dar (vgl. Näheres in <ref-ruling>76 E. 3.4.1, 4.2 und 4.3.1 S. 182 ff., 493 E. 3.2 und 3.3 S. 498 f.; <ref-ruling> E. 4.2 S. 20; s. auch Urteil 2C_36/2009 vom 20. Oktober 2009 E. 2.1 in fine).
3.4 Der Beschwerdeführer bestreitet, dass diese Voraussetzungen bei ihm erfüllt seien. Das Kantonsgericht habe in Verletzung von Art. 5 Anhang I FZA keine Prognose über die Rückfallgefahr vorgenommen. Seit seiner Einreise in die Schweiz im Jahre 2008 habe er sich wohlverhalten.
3.5 Soweit sich die Ehefrau des Beschwerdeführers auf das Freizügigkeitsabkommen berufen kann (s. E. 3.2 hievor), darf sie gegenüber Schweizer Bürgern, die den Familiennachzug verlangen, nicht diskriminiert werden (vgl. Art. 2 FZA und Art. 2 Abs. 2 AuG; <ref-ruling> E. 3.6 S. 21 f.). Nach Art. 51 Abs. 1 AuG erlöschen die Familiennachzugsansprüche von Schweizern (Art. 42 AuG), wenn sie rechtsmissbräuchlich geltend gemacht werden oder wenn Widerrufsgründe nach Art. 63 AuG vorliegen. Die Vorinstanz hält zutreffend fest, dass der Beschwerdeführer in Deutschland zu mehr als zweieinhalb Jahren Freiheitsentzug verurteilt worden ist. Damit nimmt sie zu Recht den Widerrufsgrund der längerfristigen Freiheitsstrafe gemäss Art. 62 lit. b AuG an. Dieser Widerrufsgrund ist bereits bei einer - auch im Ausland verhängten - Freiheitsstrafe von über einem Jahr erfüllt (vgl. <ref-ruling> E. 4.2 S. 379 ff.). Wohl erwähnt die Vorinstanz Art. 63 AuG nicht. Das ist hier jedoch nicht von Belang. Denn es liegt ein Widerrufsgrund nach Art. 63 Abs. 1 lit. a AuG bereits vor, wenn die Voraussetzungen des Art. 62 lit. b AuG gegeben sind.
3.6 Das Kantonsgericht äussert sich tatsächlich nicht näher zur Rückfallgefahr. Es hält aber fest, dass das kantonale Amt für Migration sowie der Regierungsrat eine nicht unerhebliche Gefahr für die öffentliche Sicherheit und Ordnung annehmen und davon ausgehen, dass das Rückfallrisiko in die Delinquenz beim Beschwerdeführer sehr hoch sei. Zudem bemerkt es, dass der Regierungsrat sämtliche Umstände des Einzelfalles berücksichtigt habe. Damit hat es die Ausführungen des Regierungsrates, auch zur Rückfallgefahr (vgl. dazu E. 4b des Beschwerdeentscheids des Regierungsrates vom 10. März 2009), zum Gegenstand seines Entscheids gemacht.
Der Beschwerdeführer legt in seiner Eingabe an das Bundesgericht nicht substantiiert dar (vgl. Art. 42 Abs. 2 , Art. 97 und Art. 106 Abs. 2 BGG), was er beim Kantonsgericht angeblich vorgebracht hat, um die vom Regierungsrat angenommene Rückfallgefahr zu widerlegen. Ein pauschaler Verweis auf die Akten und die bei den Vorinstanzen eingereichten Rechtsschriften genügt den Rüge- und Begründungsanforderungen nicht (vgl. <ref-ruling> E. 1d S. 201; Urteile des Bundesgerichts 8C_544/2007 vom 12. Februar 2008 E. 2, in: SVR 2008 UV Nr. 33 S. 124; 5A_199/2009 vom 6. Mai 2009 E. 1.2, nicht publ. in: <ref-ruling>). Daher geht die blosse Aussage des Beschwerdeführers fehl, aufgrund der Akten sei klar ersichtlich und er habe beim Kantonsgericht hinreichend nachgewiesen, dass die von ihm begangenen Delikte allesamt im Zusammenhang mit der zwischenzeitlich erfolgreich überwundenen Drogenabhängigkeit gestanden hätten. Denn zum einen ergibt sich daraus nicht, was genau er bei der Vorinstanz dargelegt haben will, das vom Kantonsgericht nicht bzw. falsch gewürdigt worden sein soll.
Zum anderen wird mit dem erwähnten Vorbringen auch nicht belegt, dass der Drogenkonsum bzw. seine diesbezügliche Sucht nicht mehr besteht. Aus den Akten ist zwar zu entnehmen, dass Urinkontrollen im Jahr 2006 ohne Auffälligkeiten geblieben waren. Angaben für die Zeit danach fehlen indes. Wie der Regierungsrat zudem bemerkt, ist aktenkundig, dass der Beschwerdeführer Anfang 2009 in der Basler Drogenszene kontrolliert wurde. Selbst wenn die Drogenabhängigkeit inzwischen überwunden sein sollte, fällt immerhin auf, dass nicht alle von ihm begangenen Delikte hierzu einen direkten Bezug hatten (z.B. mehrfaches Fahren ohne Fahrerlaubnis, Urkundenfälschung, unerlaubtes Führen einer Schusswaffe und von Munition).
Dass der Beschwerdeführer seit seiner Ankunft in der Schweiz im August 2008 keine Delikte mehr begangen haben will, erlaubt angesichts der jahrelangen deliktischen Tätigkeit noch nicht den Schluss, es gehe aktuell keine Rückfallgefahr mehr von ihm aus. Immerhin hatte er in Deutschland über viele Jahre hinweg trotz zahlreicher Verurteilungen und Massnahmen immer wieder Straftaten begangen. Deshalb wurde er neben dem Freiheitsentzug von über zweieinhalb Jahren auch zu diversen Geldstrafen von insgesamt 400 Tagessätzen verurteilt. Auch wenn es zumindest zuletzt nicht mehr um schwere, sondern um mittlere Kriminalität ging, deutet die Häufung der Verurteilungen auf Unverbesserlichkeit hin. Das ist selbst im Rahmen von Art. 5 Anhang I FZA nicht hinzunehmen. Im Übrigen hatten ihn auch die deutschen Behörden ausgewiesen. Dies hatte den Beschwerdeführer ebenso wenig vom weiteren Delinquieren abgehalten. Die deutschen Behörden hielten seinerzeit zudem fest, dass die Ausweisung selbst dann hätte verfügt werden dürfen, wenn die damals mit einer anderen deutschen Staatsangehörigen bestehende Ehe des Beschwerdeführers - deren Scheidung bevorstand - noch intakt gewesen wäre.
Soweit der Beschwerdeführer für eine Änderung seines Verhaltens auf seine aktuelle Familie verweist, ist Folgendes zu bemerken: Die Beziehung zu seiner heutigen Ehefrau bestand bereits mindestens seit dem Jahr 2004. Seit dem Jahr 2005 war er auch schon Vater der gemeinsamen Tochter T._. Weder die erwähnte Beziehung noch die Vaterschaft verhinderten das erneute Begehen von Straftaten. Daher ist sein Vorbringen, seine Familie gebe ihm Stabilität, unbehelflich.
Gegen die Annahme, der Beschwerdeführer habe sich inzwischen bewährt, spricht schliesslich auch, dass er in Deutschland noch zur Fahndung ausgeschrieben ist und er gegenüber den Schweizer Behörden wahrheitswidrig angab, nicht vorbestraft zu sein.
Selbst wenn auf vom Beschwerdeführer bei den Vorinstanzen vorgelegte - im bundesgerichtlichen Verfahren jedoch nicht ausdrücklich erwähnte - Bescheinigungen diverser deutscher Stellen abgestellt wird, ergibt sich nichts anderes. Diejenige vom 3. November 2008 betrifft ein Anti-Aggressivitäts-Training, an dem der Beschwerdeführer ab September 2002 über einen Zeitraum von sechs Monaten teilgenommen haben soll. Mehr wird darin jedoch nicht gesagt. In einem Bericht vom 11. Dezember 2006 erklärt ein Bewährungshelfer, der Beschwerdeführer vermittle in den Gesprächen glaubhaft, dass er in seinem weiteren Leben straffrei bleiben werde. Aus der vom Amt für Migration eingeholten Zentralregisterauskunft ist jedoch zu entnehmen, dass der Beschwerdeführer auch nach dem erwähnten Training und dem Bericht vom 11. Dezember 2006 wieder straffällig wurde.
3.7 Demnach ist mit den Vorinstanzen weiterhin von einer Rückfallgefahr und damit auch von einer gegenwärtigen und hinreichend schweren Gefährdung, die Grundinteressen der Gesellschaft berührt, im Sinne von Art. 5 Anhang I FZA auszugehen. Für alles Weitere, insbesondere die Verhältnismässigkeitsprüfung (vgl. Art. 96 AuG), zu der sich der Beschwerdeführer nicht näher äussert, kann auf die Ausführungen des Kantonsgerichts und des Regierungsrates verwiesen werden. Insgesamt stellt sich die Verweigerung des Familiennachzugs für den Beschwerdeführer als rechtmässig dar. Nach dem Dargelegten ergibt sich auch mit Blick auf den Schutz des Familienlebens nach Art. 8 EMRK und Art. 13 BV nichts anderes.
4. Demzufolge ist die Beschwerde unbegründet und damit abzuweisen. Diesem Ausgang entsprechend hat der Beschwerdeführer die Kosten des bundesgerichtlichen Verfahrens zu tragen (Art. 65 f. BGG). Er hat zwar unentgeltliche Rechtspflege beantragt. Wegen Aussichtslosigkeit ist dieses Gesuch jedoch abzulehnen (vgl. Art. 64 Abs. 1 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3. Die Gerichtskosten von Fr. 1'500.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Verfahrensbeteiligten, dem Kantonsgericht Basel-Landschaft, Abteilung Verfassungs- und Verwaltungsrecht, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 29. Juni 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Zünd Merz