Sachverhalt:
A. Der serbische Staatsangehörige X._ (geb. 1979) reiste am 30. Oktober 1993 unter dem Namen Y._ im Rahmen des Familiennachzugs zu seinen Eltern in die Schweiz ein, wo er im Kanton Zürich eine Aufenthaltsbewilligung erhielt. Mit Urteil des Bezirksgerichts Pfäffikon vom 7. Februar 2001 wurde er zu einer Freiheitsstrafe von zwei Jahren und einer Busse von Fr. 1'000.-- verurteilt; in der Folge verweigerte die zuständige Behörde des Kantons Zürich die Verlängerung der Aufenthaltsbewilligung und wies ihn weg. Am 7. April 2002 wurde X._ polizeilich ausgeschafft; zudem verfügte das damalige Bundesamt für Ausländerfragen (heute: Bundesamt für Migration) eine Einreisesperre auf unbestimmte Dauer.
Am 4. April 2003 heiratete X._ unter dem Namen Z._ eine in der Schweiz niedergelassene Landsfrau und reiste am 7. März 2004 im Rahmen des Familiennachzugs wieder in die Schweiz ein. Nachdem X._ mehrfach straffällig geworden war (u.a. Verurteilungen zu knapp sechs Monaten Gefängnis), verweigerten die zuständigen Behörden des Kantons Schwyz am 19. Dezember 2006 die Verlängerung der Aufenthaltsbewilligung und wiesen ihn an, die Schweiz zu verlassen. Die Ehe wurde am 19. März 2007 geschieden.
Im Kosovo liess er am 10. Juli 2007 erneut seinen Namen ändern (von Z._ in X._). Am 19. September 2007 heiratete er die kosovarische Staatsangehörige A._ (geb. 1984), die in der Schweiz über eine Niederlassungsbewilligung verfügt. Am 30. Mai 2008 reiste er im Rahmen des Familiennachzugs - erneut unter Missachtung des Einreiseverbots - in die Schweiz ein und erhielt im Kanton Luzern eine Aufenthaltsbewilligung. Am 15. August 2009 kam die gemeinsame Tochter B._ zur Welt.
B. Am 18. Januar 2010 wies das Bundesamt für Migration (BFM) ein Gesuch von X._ um Aufhebung der Einreisesperre ab; zudem wies das BFM darauf hin, dass der Aufenthalt von X._ nicht weiter zu verlängern sei. Mit Verfügung vom 8. März 2010 verweigerte das Amt für Migration des Kantons Luzern X._ die Verlängerung der Aufenthaltsbewilligung und ordnete seine Wegweisung an. Die dagegen erhobene Beschwerde wies das Justiz- und Sicherheitsdepartement des Kantons Luzern am 7. September 2010 ab. Das Verwaltungsgericht des Kantons Luzern wies die dagegen erhobene Beschwerde am 24. Oktober 2011 ab, soweit es darauf eintrat.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 5. Dezember 2011 beantragt X._, das Urteil vom 24. Oktober 2011 sei aufzuheben und es sei ihm der weitere Aufenthalt in der Schweiz zu gestatten, eventualiter sei die Streitsache an die Vorinstanz zurückzuweisen.
Das Verwaltungsgericht des Kantons Luzern und das Bundesamt für Migration beantragen die Abweisung der Beschwerde. Das Amt für Migration und das Justiz- und Sicherheitsdepartement des Kantons Luzern haben sich nicht vernehmen lassen.
D. Mit Verfügung vom 8. Dezember 2011 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt.
Erwägungen:
1. 1.1 Ausländische Ehegatten von Niedergelassenen haben unter Vorbehalt von Widerrufsgründen Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, wenn sie mit ihrem Partner zusammenwohnen (Art. 43 Abs. 1 in Verbindung mit Art. 51 Abs. 2 und 62 AuG [SR 142.20]). Ein identischer Anspruch ergibt sich im vorliegenden Fall aus Art. 8 EMRK bzw. Art. 13 Abs. 1 BV (Schutz des Familienlebens), da die Ehegattin und die Tochter mit ihren Niederlassungsbewilligungen hier über ein gefestigtes Anwesenheitsrecht verfügen und der Beschwerdeführer seine intakten familiären Beziehungen zu ihnen tatsächlich lebt (BGE 130 II 281 E. 3.1 S. 285 f.).
Gegen den angefochtenen kantonal letztinstanzlichen Endentscheid ist die Beschwerde an das Bundesgericht somit zulässig (Art. 83 lit. c Ziff. 2, 86 Abs. 1 lit. d und 90 BGG).
1.2 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat. Es kann die Sachverhaltsfeststellung der Vorinstanz von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht (Art. 105 Abs. 1 und 2 BGG). Die Rüge, der Sachverhalt sei offensichtlich unrichtig festgestellt (Art. 97 Abs. 1 BGG) muss in der Beschwerdeschrift nach den Anforderungen gemäss Art. 106 Abs. 2 BGG vorgebracht und begründet werden (BGE 133 II 249 E. 1.4.3 S. 254 f.).
2. 2.1 Nicht durchzudringen vermag vorab die Rüge, die Vorinstanz habe den Anspruch auf rechtliches Gehör verletzt, indem sie die Ehefrau nicht (noch einmal) befragt habe. Zwar umfasst der in Art. 29 Abs. 2 BV gewährleistete Anspruch auf rechtliches Gehör u.a. auch das Recht der Betroffenen, mit erheblichen Beweisanträgen gehört zu werden (BGE 135 II 286 E. 5.1 S. 293 mit Hinweisen). Jedoch ist dieser Anspruch nicht verletzt, wenn ein Gericht deshalb auf die Abnahme beantragter Beweismittel verzichtet, weil es aufgrund der bereits abgenommenen Beweise seine Überzeugung gebildet hat und ohne Willkür in vorweggenommener (antizipierter) Beweiswürdigung annehmen kann, dass seine Überzeugung durch weitere Beweiserhebungen nicht geändert würde (BGE 134 I 140 E. 5.3 S. 148 mit Hinweisen). Diese Voraussetzungen waren vorliegend ohne Weiteres erfüllt: Die Aussagen der Ehefrau sowie des Beschwerdeführers liegen den Akten bei und sind von der Vorinstanz gewürdigt worden (vgl. angefochtener Entscheid E. 6f). Der Beschwerdeführer hatte zudem genügend Gelegenheit, sich zu äussern und allenfalls weitere geeignete Belege einzureichen, um seinen Standpunkt darzulegen.
2.2 Soweit der Beschwerdeführer sodann auf Ausführungen vor den Vorinstanzen verweist (vgl. insb. Beschwerdeschrift Ziff. 1.4), tritt das Bundesgericht praxisgemäss nicht darauf ein. Die erhobenen Rügen müssen in der Beschwerdeschrift selber enthalten sein; der blosse Verweis auf Ausführungen in anderen Rechtsschriften oder auf die Akten reicht nicht aus (BGE 133 II 396 E. 3.1 S. 399 f. mit Hinweisen).
3. 3.1 Nach Art. 62 lit. a AuG kann die Aufenthaltsbewilligung widerrufen werden, wenn der Ausländer oder sein Vertreter im Bewilligungsverfahren falsche Angaben macht oder wesentliche Tatsachen verschwiegen hat. Das Bundesgericht hat ausgeführt, dass die unter dem alten Recht (Art. 9 Abs. 2 lit. a und Abs. 4 lit. a ANAG) zu diesem Widerrufsgrund entwickelte Praxis im Wesentlichen auch für Art. 62 lit. a AuG gilt. Namentlich muss die falsche Angabe oder das Verschweigen wesentlicher Tatsachen in der Absicht erfolgt sein, gestützt darauf den Aufenthalt oder die Niederlassung bewilligt zu erhalten. Der Ausländer ist verpflichtet, den Behörden wahrheitsgetreu über alles Auskunft zu geben, was für den Bewilligungsentscheid massgebend sein kann (Art. 3 Abs. 2 und Art. 13f ANAG bzw. Art. 90 AuG). Wesentlich sind nicht nur Umstände, nach denen die Fremdenpolizei ausdrücklich fragt, sondern auch solche, von denen der Gesuchsteller wissen muss, dass sie für den Bewilligungsentscheid massgeblich sein können (Urteile 2C_656/2011 vom 8. Mai 2012 E. 2.1; 2C_15/2011 vom 31. Mai 2011 E. 4.2.1).
3.2 Der Schluss der Vorinstanz, wonach im vorliegenden Fall der Widerrufsgrund von Art. 62 lit. a AuG erfüllt ist, ist nicht zu beanstanden.
3.2.1 So hat die Vorinstanz festgestellt, dass in den vom Beschwerdeführer im Bewilligungsverfahren eingereichten Geburts- und Heiratsurkunden nicht nur der Name des Beschwerdeführers, sondern auch jeweils der Nachname der Eltern abgeändert worden ist. Zudem hat der Beschwerdeführer bereits beim Ausfüllen des Visumsantrags für die Schweiz am 11. April 2008 wahrheitswidrige Angaben gemacht, indem er seine früheren Aufenthalte in der Schweiz verschwiegen hat. Der Vorinstanz ist zuzustimmen, wenn sie ausführt, der Beschwerdeführer habe sich der drohenden Konsequenzen einer Einreise unter falschem Namen bewusst sein müssen. Trotzdem hat es der Beschwerdeführer unterlassen, seine früheren Identitäten und Aufenthalte in der Schweiz gegenüber den Behörden offen zu legen. Ebenso zutreffend sind die Ausführungen der Vorinstanz auf den wenig überzeugenden Einwand des Beschwerdeführers, er habe nicht gewusst, wie er sich nach einer Namensänderung verhalten müsse: Der Beschwerdeführer ist insgesamt zweimal mit einem geänderten Namen in die Schweiz eingereist und bereits der Kanton Schwyz hat die Aufenthaltsbewilligung unter anderem aufgrund der Einreise mit geändertem Namen verweigert (vgl. angefochtener Entscheid E. 4d).
3.2.2 Der Beschwerdeführer setzt sich mit den Erwägungen der Vorinstanz über den Widerrufsgrund von Art. 62 lit. a AuG nicht substantiell auseinander, so dass es fraglich ist, ob die Beschwerde in diesem Punkt überhaupt den Begründungsanforderungen von Art. 42 Abs. 2 BGG genügt.
Der Beschwerdeführer beschränkt sich im Wesentlichen auf die Rüge, in Bezug auf die Umgehung der Einreisesperre habe die Vorinstanz den Sachverhalt offensichtlich unrichtig festgestellt. Daraus kann der Beschwerdeführer jedoch nichts zu seinen Gunsten ableiten: Zwar hat die zuständige Staatsanwaltschaft am 5. August 2010 aus formellen Gründen (keine Rechtswirkung der Einreisesperre "mangels einer belegbaren gültigen Eröffnung") das Strafverfahren betreffend Widerhandlungen gegen das AuG eingestellt, gleichzeitig aber festgehalten, dass "der Angeschuldigte trotz offensichtlicher Kenntnis der Einreisesperre nach der Namensänderung in die Schweiz einreiste". Zudem ist im vorliegenden Fall der Widerrufsgrund erfüllt, weil der Beschwerdeführer seine früheren Aufenthalte, Verurteilungen und Namensänderungen verschwiegen hat; dem allenfalls zusätzlich gegebenen Verstoss gegen die Einreisesperre kommt hier somit keine entscheidende Bedeutung mehr zu.
4. 4.1 Wenn ein Ausländer durch sein Verhalten einen Widerrufsgrund gesetzt hat, bleibt zu prüfen, ob diese Massnahme auch als verhältnismässig erscheint. Dabei sind namentlich die Schwere des Verschuldens, der Grad der Integration sowie die dem Betroffenen drohenden Nachteile zu berücksichtigen (BGE 135 II 377 E. 4.3 ff. S. 381 ff.; vgl. auch Art. 96 Abs. 1 AuG). Nach der Rechtsprechung des Bundesgerichts sind umso strengere Anforderungen an eine fremdenpolizeiliche Massnahme zu stellen, je länger ein Ausländer in der Schweiz anwesend war. Selbst bei einem Ausländer, der bereits hier geboren ist und sein ganzes bisheriges Leben in der Schweiz verbracht hat (Ausländer der zweiten Generation), sind fremdenpolizeiliche Massnahmen aber nicht ausgeschlossen (BGE 122 II 433 E. 2c S. 436; 130 II 176 E. 4.4.2 S. 190).
Die Notwendigkeit einer Verhältnismässigkeitsprüfung ergibt sich auch aus Art. 8 Ziff. 2 EMRK, soweit ein Eingriff in das von Art. 8 Ziff. 1 EMRK geschützte Privat- und Familienleben vorliegt; ein solcher ist dann statthaft, wenn er gesetzlich vorgesehen ist und eine Massnahme darstellt, die in einer demokratischen Gesellschaft für die nationale Sicherheit, die öffentliche Ordnung, das wirtschaftliche Wohl des Landes, die Verteidigung der Ordnung oder zur Verhinderung von strafbaren Handlungen, zum Schutz der Gesundheit und Moral sowie der Rechte und Freiheiten anderer notwendig erscheint. Bei der Interessenabwägung im Rahmen von Art. 8 Ziff. 2 EMRK sind - wie bei jener nach Art. 11 Abs. 3 ANAG bzw. nach Art. 96 Abs. 1 AuG - die Schwere des begangenen Delikts, der seit der Tat vergangene Zeitraum, das Verhalten des Ausländers während dieser Periode, die Auswirkungen auf die primär betroffene Person sowie deren familiäre Situation zu berücksichtigen (BGE 135 II 377 E. 4.3 S. 381 mit Hinweisen).
4.2 Das öffentliche Interesse an der Fernhaltung des Beschwerdeführers hat die Vorinstanz zu Recht bejaht: Dabei fällt neben dem bereits erwähnten Verschweigen von wesentlichen Tatsachen bzw. dem Machen falscher Angaben zusätzlich vor allem die immer wiederkehrende Straffälligkeit des Beschwerdeführers ins Gewicht. So wurde er 2001 vom Bezirksgericht Pfäffikon wegen gewerbs- und bandenmässigen Diebstahls, falscher Anschuldigung, Nötigung, mehrfacher Sachbeschädigung, mehrfachen Hausfriedensbruchs, Entwendung zum Gebrauch, Missbrauchs von Ausweisen und Schildern, mehrfachen Fahrens ohne Führerausweis sowie der mehrfachen Verletzung der Verkehrsregeln zu einer Freiheitsstrafe von zwei Jahren und einer Busse von Fr. 1'000.-- verurteilt. In den Jahren 2002 bis 2010 kamen Strafen von insgesamt knapp sechs Monaten Gefängnis sowie mehrere Strafverfügungen dazu, darunter ein Sicherungsentzug des Führerausweises. Dieses deliktische Verhalten - wie schon das Erschleichen der Aufenthaltsbewilligung durch Täuschung der Schweizer Behörden - zeigt, dass der Beschwerdeführer nicht gewillt ist, sich an die in der Schweiz geltenden Gesetze und Regeln zu halten. Es besteht damit ein gewichtiges ordnungs- und sicherheitspolizeiliches Interesse an der Fernhaltung des Beschwerdeführers.
4.3 Die gegenläufigen privaten Interessen des Beschwerdeführers am Verbleib in der Schweiz fallen demgegenüber - wie die Vorinstanz zu Recht ausgeführt hat - weniger ins Gewicht. Gegen seine Ausweisung spricht zwar der Umstand, dass der Beschwerdeführer, welcher im Familiennachzug in die Schweiz kam, bereits im Alter von 14 Jahren in die Schweiz einreiste. Allerdings wurde er seit der ersten Einreise bereits zwei Mal (2001 und 2006) wieder aus der Schweiz weggewiesen und lebte jeweils knapp zwei Jahre in seiner Heimat. Von den 14 Jahren, die insgesamt in der Schweiz verbracht hat, befand er sich zudem zwei Jahre im Strafvollzug. Er ist auch kein Ausländer der zweiten Generation. Trotz einer mittleren Aufenthaltsdauer kann auch nicht von einer besonders guten Integration des Beschwerdeführers und schon gar nicht von einer Verwurzelung in der Schweiz gesprochen werden. Immerhin arbeitet er in ungekündigter Stellung und ist auch im Betreibungsregister nicht verzeichnet. In sozialer und kultureller Hinsicht lässt der Beschwerdeführer hingegen keine Verbundenheit mit der schweizerischen Gesellschaft erkennen. Die Beziehungen zu seinen in der Schweiz lebenden Familienangehörigen vermochten ihn offenbar auch nicht davon abzuhalten, immer wieder Delikte zu begehen. Im Übrigen ist davon auszugehen, dass ihm Kultur und Gepflogenheiten seines Heimatlandes, wo er seine Kindheit verbracht und einen Teil der Grundschule absolviert hat, durch sein Elternhaus vermittelt worden und somit nicht gänzlich unvertraut sind. Der blosse Umstand, dass die allgemeinen und wirtschaftlichen Lebensverhältnisse in seiner Heimat weniger günstig sein mögen als in der Schweiz, macht eine Rückreise nicht unzumutbar (Urteile 2A.469/2005 vom 28. November 2005 E. 2.3; 2A.157/1998 vom 17. Juni 1998 E. 3c). Dem Beschwerdeführer ist folglich zuzumuten, dorthin auszureisen.
4.4 Zu prüfen bleiben die Auswirkungen des angefochtenen Entscheids auf die familiären Beziehungen: Der Beschwerdeführer rügt eine Verletzung von Art. 8 EMRK bzw. Art. 13 BV (Recht auf Achtung des Privat- und Familienlebens). Zwar fallen die Beziehungen des Beschwerdeführers zu seiner Ehefrau und seiner Tochter zweifellos in den Schutzbereich von Art. 8 EMRK bzw. Art. 13 BV. Die Vorinstanz hat dazu festgehalten, dass die Ehefrau im Kosovo geboren ist, aber fast ihr ganzes Leben in der Schweiz verbracht hat. Die Tochter ist heute drei Jahre alt und befindet sich damit noch in einem anpassungsfähigen Alter. Die Vorinstanz hat daraus zu Recht geschlossen, die Ausreise wäre für die Ehefrau und Tochter mit grossen Nachteilen verbunden. Ob sie auch zumutbar ist, kann hier letztlich offen bleiben: Wie die Vorinstanz zu Recht ausgeführt hat, steht es Ehefrau und Kindern grundsätzlich frei, ob sie in der Schweiz verbleiben oder ihrem Ehemann und Vater in den Kosovo folgen wollen. Ob die gesellschaftliche Realität diese Wahlmöglichkeit zulässt, braucht hier nicht näher geprüft zu werden, da selbst die Unzumutbarkeit der Ausreise für die Angehörigen nicht notwendigerweise zur Unzulässigkeit des Widerrufs führt: Bei einem mit einer Schweizerin verheirateten Ausländer, der erstmals um eine Bewilligung ersucht oder nach bloss kurzer Aufenthaltsdauer die Bewilligung erneuern lassen will, geht die Rechtsprechung davon aus, dass die Grenze, von der an in der Regel auch dann keine Bewilligung mehr erteilt wird, wenn der Ehefrau die Ausreise aus der Schweiz unzumutbar oder nur schwer zumutbar ist, bei zwei Jahren Freiheitsstrafe liegt (BGE 135 II 377 E. 4.4 S. 382 mit Hinweisen; sog. Reneja-Praxis nach BGE 110 Ib 201). Zwar bildet diese "Zwei-Jahres-Regel" keine starre Grenze, sondern ist im Sinne einer Vergleichsgrösse bzw. eines Richtwertes in die Verhältnismässigkeitsprüfung mit einzubeziehen (vgl. Urteile 2C_264/2011 vom 15. November 2011 E. 5.3; 2C_825/2008 vom 7. Mai 2009 E. 3.3); entscheidend sind dabei stets die Umstände des Einzelfalls (BGE 120 Ib 6 E. 4b S. 14; 135 II 377 E. 4.4 S. 383). Ist der Ehegatte aber nicht Schweizer Bürger, sondern - wie vorliegend - ebenfalls ausländischer Staatsangehöriger, ist diese Praxis nicht bzw. verschärft anwendbar, d.h. auch bei einer kürzeren Freiheitsstrafe ist ungeachtet der Zumutbarkeit für die Angehörigen eine Nichtverlängerung bzw. eine Ausweisung möglich (Urteile 2C_389/2011 vom 22. Dezember 2011 E. 3.2.6; 2C_915/2010 vom 4. Mai 2011 E. 4; 2C_148/2009 vom 6. November 2009 E. 2.2; 2A.640/1998 vom 22. Februar 1999 E. 2b/bb; 2A.580/1996 vom 22. Januar 1997 E. 1d). Dies gilt umso mehr im vorliegenden Fall bei einer Freiheitsstrafe von total zwei Jahren und knapp sechs Monaten.
Hier liegt der Widerrufsgrund zwar nicht primär in der hiesigen deliktischen Betätigung (Art. 62 lit. b AuG), sondern im Verschweigen vorbestehender, entscheidwesentlicher Tatsachen (Art. 62 lit. a AuG). Verschweigt die um eine Bewilligung ersuchende ausländische Person die Existenz früherer Aufenthalte, Verurteilungen sowie Namensänderungen, so verletzt sie die ihr obliegende Mitwirkungspflicht in schwerwiegender Weise, was nicht zu schützen ist (vgl. Urteil 2C_136/2012 vom 17. April 2012 E. 5.3).
4.5 Gesamthaft betrachtet ist der Schluss der Vorinstanz nicht zu beanstanden, wonach die ordnungs- und sicherheitspolizeilichen Interessen an der Fernhaltung des Ausländers die privaten Interessen der Beteiligten überwiegen. Daraus ergibt sich, dass der angefochtene Entscheid Art. 8 EMRK bzw. Art. 13 BV nicht verletzt.
Im Weiteren ist zwar ebenfalls das Wohl des Kindes zu berücksichtigen, wie der Beschwerdeführer sinngemäss geltend macht (vgl. Art. 3 des Übereinkommens vom 20. November 1989 über die Rechte des Kindes (UNO-KRK; SR 0.107). Über Art. 8 EMRK hinaus gehende Ansprüche auf Bewilligung ergeben sich aus der Kinderrechtskonvention jedoch nicht (vgl. BGE 124 II 361 E. 3b S. 367 f.; Urteile 2C_578/2011 vom 1. Dezember 2011 E. 3.4.7; 2C_62/2010 vom 30. August 2010 E. 2.3).
5. 5.1 Die Beschwerde erweist sich somit als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Ergebnis besteht auch kein Anlass, dem Eventualantrag (Rückweisung der Sache an die Vorinstanz zur Neubeurteilung) bzw. dem Antrag auf eine "angemessene Parteientschädigung für die zwei Vorverfahren" stattzugeben.
5.2 Bei diesem Verfahrensausgang sind die bundesgerichtlichen Kosten dem unterliegenden Beschwerdeführer aufzuerlegen (Art. 65 und 66 Abs. 1 BGG). Eine Parteientschädigung ist nicht zuzusprechen (Art. 68 BGG).
Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Luzern, Verwaltungsrechtliche Abteilung, sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 23. August 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Winiger