Sachverhalt:
A. A.a X._, geboren am 5. April 1985, stammt aus Mazedonien. Am 29. Januar 1991 reiste er im Familiennachzug zum Verbleib bei den Eltern in die Schweiz ein. Er ist im Besitz einer Niederlassungsbewilligung mit Kontrollfrist bis zum 2. Juli 2014. Eine am 6. Juli 2006 in Mazedonien geschlossene Ehe mit seiner Landsfrau Y._ wurde am 12. November 2008 wieder geschieden. Am 26. August 2011 ehelichte X._ die in der Schweiz niedergelassene Z._ aus Serbien und Montenegro, geboren am 30. Dezember 1985.
A.b Zwischen April 2001 und Juli 2010 wurde X._ wiederholt straffällig. Die gemäss dem Jugendstrafrecht verfolgten Taten betrafen Raub (Einschliessung von 30 Tagen), fahrlässige Verursachung einer Feuersbrunst (Verweis) sowie Tätlichkeiten und Diebstahl (Einschliessung von vier Tagen).
Als junger Erwachsener verübte X._ zunächst folgende Straftaten, welche zu Freiheitsstrafen führten:
Urteil des Bezirksgerichts Horgen vom 15. März 2006: 16 Monate Gefängnis wegen gewerbs- und bandenmässigen Diebstahls, mehrfacher Sachbeschädigung, mehrfachen Hausfriedensbruchs, Entwendung eines Motorfahrzeugs zum Gebrauch und Missbrauchs von Ausweisen und Schildern;
Urteil des Bezirksgerichts Horgen vom 8. November 2006: Ein Monat Gefängnis als Zusatzstrafe zum Urteil des Bezirksgerichts Horgen vom 15. März 2006 wegen Diebstahls, Sachbeschädigung und Hausfriedensbruchs.
Am 23. Oktober 2007 drohte die Fremdenpolizei des Kantons Schwyz (heute: Amt für Migration) X._ die Ausweisung an für den Fall, dass er erneut verurteilt würde oder sein Verhalten zu anderen berechtigten Klagen Anlass geben sollte.
In der Folge kam es neben verschiedenen Bussenverfügungen zu folgenden Verurteilungen:
Urteil des Bezirksgerichts Horgen vom 3. Dezember 2008: Freiheitsstrafe von acht Monaten und Busse von Fr. 600.-- wegen mehrfacher grober Verletzung der Verkehrsregeln, Fahrens in fahrunfähigem Zustand, versuchter Vereitelung von Massnahmen zur Feststellung der Fahrunfähigkeit und Übertretung des Betäubungsmittelgesetzes;
Strafbescheid der Staatsanwaltschaft des Kantons St. Gallen vom 27. Januar 2009: Vier Monate Freiheitsstrafe als Zusatzstrafe zum Urteil des Bezirksgerichts Horgen vom 3. Dezember 2008 wegen mehrfachen Diebstahls, mehrfacher Sachbeschädigung und mehrfachen Hausfriedensbruchs;
Verfügung des Verkehrsamtes des Kantons Schwyz vom 8. Juli 2010: Vorsorglicher Sicherungsentzug des Führerausweises und Anordnung eines verkehrsmedizinischen Untersuchs wegen Lenkens eines Personenwagens am 31. Mai 2010 unter Drogeneinfluss;
Strafbefehl der Oberstaatsanwaltschaft des Kantons Schwyz vom 31. März 2011: Sechs Monate Freiheitsstrafe und Fr. 300.-- Busse als teilweise Zusatzstrafe zum Urteil des Bezirksgerichts Horgen vom 3. Dezember 2008 und zum Strafbescheid der Staatsanwaltschaft des Kantons St. Gallen vom 27. Januar 2009 wegen mehrfachen Diebstahls, einfacher Sachbeschädigung, qualifizierter Sachbeschädigung, mehrfachen Hausfriedensbruchs, Führens eines Motorfahrzeugs in fahrunfähigem Zustand, Entwendung eines Motorfahrzeugs zum Gebrauch und mehrfacher Widerhandlung gegen das Betäubungsmittelgesetz zwischen Sommer 2008 und März 2009.
A.c Gemäss Betreibungsregisterauszug vom 26. August 2010 beliefen sich X._s Privatschulden auf knapp Fr. 35'000.--, wobei den Gläubigern in der Mehrzahl der Fälle ein Verlustschein ausgestellt wurde.
B. Am 3. Dezember 2010 teilte das Amt für Migration X._ mit, es ziehe in Erwägung, die bis zum 2. Juli 2014 gültige Niederlassungsbewilligung zu widerrufen, und gewährte ihm das rechtliche Gehör.
Mit Verfügung vom 7. Januar 2011 widerrief das Amt für Migration die Niederlassungsbewilligung und wies X._ aus der Schweiz weg.
Die dagegen erhobenen Rechtsmittel blieben erfolglos (vgl. Beschluss des Regierungsrates des Kantons Schwyz vom 23. August 2011 und Entscheid des Verwaltungsgerichts des Kantons Schwyz vom 23. November 2011).
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten, eventuell subsidiärer Verfassungsbeschwerde vom 16. Januar 2012 stellt X._ vor Bundesgericht die Anträge, der Entscheid des Verwaltungsgerichts des Kantons Schwyz sei vollumfänglich aufzuheben und es sei vom Widerruf der Niederlassungsbewilligung abzusehen, eventuell sei das Verfahren zur Neubeurteilung an die Vorinstanz zurückzuweisen.
Das Verwaltungsgericht und der Regierungsrat des Kantons Schwyz sowie das Bundesamt für Migration beantragen die Abweisung der Beschwerde. Das Amt für Migration verzichtet auf eine Vernehmlassung.
Mit Eingabe vom 18. Mai 2012 teilt der Beschwerdeführer mit, seine Ehefrau habe am 26. April 2012 die gemeinsame Tochter W._ zur Welt gebracht, und beantragt die Berücksichtigung dieser neuen Tatsache im bundesgerichtlichen Verfahren.
Der Beschwerdeführer lässt sich mit Bemerkungen vom 29. Juni 2012 zu den Beschwerdeantworten vernehmen.
D. Mit Präsidialverfügung vom 20. Januar 2012 ist der Beschwerde antragsgemäss aufschiebende Wirkung erteilt worden.
Erwägungen:
1. Angefochten ist der letztinstanzliche, verfahrensabschliessende Entscheid eines kantonalen Gerichts auf dem Gebiet des öffentlichen Rechts, welcher grundsätzlich der Beschwerde in öffentlich-rechtlichen Angelegenheiten unterliegt (vgl. Art. 86 Abs. 1 lit. d BGG, Art. 90 BGG, Art. 82 lit. a BGG). Gegen Entscheide über den Widerruf einer Niederlassungsbewilligung ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig, weil grundsätzlich ein Anspruch auf das Fortbestehen dieser Bewilligung gegeben ist (BGE 135 II 1 E. 1.2.1 S. 4). Ob der Anspruch auf Aufhebung des Widerrufs im konkreten Fall zu bejahen ist, betrifft nicht die Eintretensfrage, sondern die materielle Behandlung der Beschwerde (BGE 136 II 177 E. 1.1 S. 179). Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist somit zulässig. Demgemäss bleibt für die subsidiäre Verfassungsbeschwerde kein Raum, weshalb darauf nicht einzutreten ist (vgl. Art. 113 BGG).
2. 2.1 Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann u.a. die Verletzung von Bundesrecht (inklusive Bundesverfassungsrecht) und Völkerrecht gerügt werden (Art. 95 lit. a und b BGG). Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden (BGE 133 II 249 E. 1.4.1 S. 254). In Bezug auf die Verletzung von Grundrechten gilt eine qualifizierte Rüge- und Substanziierungspflicht (Art. 106 Abs. 2 BGG; BGE 133 II 249 E. 1.4.2 S. 254).
2.2 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (Art. 105 Abs. 1 BGG). Die Feststellung des Sachverhalts kann nur beanstandet bzw. vom Bundesgericht von Amtes wegen berichtigt oder ergänzt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinn von Art. 95 BGG beruht (Art. 97 Abs. 1 BGG bzw. Art. 105 Abs. 2 BGG). Eine entsprechende Rüge, welche rechtsgenüglich substanziiert vorzubringen ist (Art. 42 Abs. 2 BGG; vgl. BGE 133 II 249 E. 1.4.3 S. 254), setzt zudem voraus, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 BGG).
2.3 Neue Tatsachen und Beweismittel dürfen nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (Art. 99 Abs. 1 BGG). Tatsachen, welche sich erst nach Erlass des angefochtenen Entscheids ereignet haben (echte Noven), sind in jedem Fall unbeachtlich, da sie von vornherein nicht durch den vorinstanzlichen Entscheid veranlasst sein können (Urteil 2C_833/2011 vom 6. Juni 2012 E. 1.2).
Der Beschwerdeführer weist in seiner Beschwerde auf die Schwangerschaft seiner Ehefrau hin und beantragt replikweise, die am 26. April 2012 erfolgte Geburt der gemeinsamen Tochter W._ zu berücksichtigen. Obwohl die Schwangerschaft bereits im vorinstanzlichen Verfahren geltend gemacht und belegt wurde, stellt die Geburt der Tochter ein echtes Novum dar und kann daher im Verfahren vor dem Bundesgericht nicht berücksichtigt werden. Hingegen ist der Tatsache, dass die Ehefrau im Zeitpunkt des angefochtenen Entscheids schwanger war, gebührend Rechnung zu tragen.
3. 3.1 Der Beschwerdeführer macht eine Verletzung seines Anspruchs auf rechtliches Gehör geltend.
Die Vorinstanz habe ausgeführt, sowohl seine erste als auch seine zweite Ehefrau stamme aus dem gleichen Kulturkreis wie er, was eine echte Integration auch künftig nicht erleichtern werde. Da die Vorinstanz diese Feststellung als entscheidrelevant betrachtet habe, hätte sie ihm Gelegenheit geben müssen, zum "Kulturkreis" seiner Ehefrau Ausführungen zu machen. Weiter habe die Vorinstanz erwogen, für den behaupteten mehrheitlichen Kontakt zu Schweizern fehle es an rechtsgenüglichen Belegen. Er - der Beschwerdeführer - sei jedoch weder im Verfahren vor dem Amt für Migration noch im vorinstanzlichen Verfahren aufgefordert worden, seine Angaben mit Belegen zu untermauern. Deswegen müsse ihm Gelegenheit gegeben werden, bezüglich seiner Kontakte zu Schweizern Belege einzureichen bzw. Zeugen zu nennen.
3.2 Das rechtliche Gehör gemäss Art. 29 Abs. 2 BV dient einerseits der Sachaufklärung, andererseits stellt es ein persönlichkeitsbezogenes Mitwirkungsrecht beim Erlass eines Entscheids dar, welcher in die Rechtsstellung des Einzelnen eingreift. Dazu gehört insbesondere das Recht des Betroffenen, sich vor Erlass eines solchen Entscheids zur Sache zu äussern, erhebliche Beweise beizubringen, Einsicht in die Akten zu nehmen, mit erheblichen Beweisanträgen gehört zu werden und an der Erhebung wesentlicher Beweise entweder mitzuwirken oder sich zumindest zum Beweisergebnis zu äussern, wenn dieses geeignet ist, den Entscheid zu beeinflussen. Der Anspruch auf rechtliches Gehör umfasst als Mitwirkungsrecht somit alle Befugnisse, die einer Partei einzuräumen sind, damit sie in einem Verfahren ihren Standpunkt wirksam zur Geltung bringen kann (BGE 135 II 286 E. 5.1 S. 293 mit Hinweisen).
3.3 Die Vorinstanz hat bei der Würdigung der Integration des Beschwerdeführers den Umstand, dass die Ehefrau aus Serbien stammt, zur Begründung ihres Urteils herangezogen. Ob die Auslegung des Begriffs "Kulturkreis" in diesem Zusammenhang zutreffend ist, kann offen bleiben (vgl. auch E. 4.4), zumal der Begründung ohnehin nicht gefolgt werden kann (vgl. E. 7.2). Für die Zweifel der Vorinstanz an der künftigen "echten" Integration des Beschwerdeführers war nicht die Frage massgeblich, ob Mazedonien und Serbien zum gleichen Kulturkreis gehören, sondern die (unbestrittene) Tatsache, dass der Beschwerdeführer und seine Frau aus dem Balkan stammen. Deswegen war die Vorinstanz nicht gehalten, dem Beschwerdeführer dieses Begründungselement vorab mitzuteilen.
3.4 Im Gegensatz zu dem, was der Beschwerdeführer vorbringt, wurde ihm die Mitwirkung an den vorinstanzlichen Entscheiden des Amts für Migration nicht verweigert. In beiden Verfahren, insbesondere bei der entsprechenden Befragung durch das Amt für Migration, stand es ihm frei, Fakten betreffend seine Integration geltend zu machen. Weder das Amt für Migration noch die Vorinstanz haben das rechtliche Gehör des Beschwerdeführers verletzt, indem sie seine Antworten auf Fragen betreffend die Integration zu seinen Ungunsten würdigten. Es geht nicht darum, dass vom Beschwerdeführer zusätzliche "Belege" erwartet wurden, wie er meint, sondern darum, dass er das Amt für Migration in Bezug auf seine soziale Integration nicht zu überzeugen vermochte und dass die Vorinstanz die Einschätzung des Amts für Migration geschützt hat.
4. 4.1 Der Beschwerdeführer rügt sodann eine willkürliche Feststellung des rechtserheblichen Sachverhalts.
4.2 Die Vorinstanz habe Art. 9 BV verletzt, indem sie in aktenwidriger Weise festgestellt habe, der Beschwerdeführer und seine Ehefrau würden dem gleichen Kulturkreis angehören. Ebenfalls aktenwidrig und willkürlich sei die Feststellung der Vorinstanz, wonach die Oberstaatsanwaltschaft des Kantons Schwyz dem Beschwerdeführer im Strafbefehl vom 31. März 2011 keine günstige Prognose ausgestellt habe.
4.3 Nach der ständigen Praxis des Bundesgerichts liegt Willkür in der Rechtsanwendung vor, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist. Dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, genügt nicht (BGE 138 I 49 E. 7.1 S. 51; 137 I 1 E. 2.4 S. 5).
4.4 Der Begriff "Kulturkreis" wird nicht nur in der Umgangssprache, sondern auch in den Geisteswissenschaften unterschiedlich definiert. Deswegen kann in der Auffassung der Vorinstanz, wonach Mazedonien und Serbien zum gleichen Kulturkreis gehören, keine willkürliche Auslegung des Begriffs und folglich keine willkürliche Sachverhaltsfeststellung erblickt werden.
4.5 Auch die Rüge, die Vorinstanz habe die Prognose der Oberstaatsanwaltschaft des Kantons Schwyz vom 31. März 2011 willkürlich gewürdigt, ist nicht zu hören. Die Oberstaatsanwaltschaft des Kantons Schwyz begründete im Strafbefehl vom 31. März 2011 ihre Einschätzung, wonach die Voraussetzungen für die Gewährung des bedingten Strafvollzugs nicht erfüllt seien, folgendermassen: Der Beschwerdeführer sei binnen fünf Jahren seit der letzten Verurteilung mit einem Strafmass von acht Monaten Freiheitsstrafe wieder straffällig geworden; besonders günstige Umstände einer guten Prognose seien nicht auszumachen.
Richtig ist, dass die Oberstaatsanwaltschaft des Kantons Schwyz damit nicht direkt das Rückfallrisiko angesprochen, sondern die Notwendigkeit des unbedingten Strafvollzugs begründet hat. Gerade die Begründung aber legt es nahe, für die Zukunft von einer nicht besonders günstigen, also tendenziell ungünstigen Prognose auszugehen. Mit Blick auf die von der Oberstaatsanwaltschaft des Kantons Schwyz erwähnte wiederholte Begehung mehrerer Straftaten geht die Interpretation des Beschwerdeführers, die Strafbehörde habe dem Beschwerdeführer eine günstige Prognose ausgestellt, eindeutig fehl. Die Vorinstanz hat gestützt auf die entsprechende Erwägung der Strafbehörde ein Rückfallrisiko bejaht; von einer willkürlichen Würdigung der Prognose kann nicht gesprochen werden.
5. 5.1 Gemäss Art. 63 Abs. 1 lit. a AuG in Verbindung mit Art. 62 lit. b AuG kann die Niederlassungsbewilligung widerrufen werden, wenn die ausländische Person zu einer längerfristigen Freiheitsstrafe verurteilt oder gegen sie eine strafrechtliche Massnahme angeordnet wurde. Nach der bundesgerichtlichen Rechtsprechung fällt unter den Begriff der längerfristigen Freiheitsstrafe jede Freiheitsstrafe von mehr als einem Jahr (BGE 135 II 377 E 4.2), wobei die Strafe sich zwingend auf ein einziges Strafurteil stützen muss (BGE 137 II 297 E. 2). Da der Beschwerdeführer rechtskräftig zu einer Freiheitsstrafe von 16 Monaten verurteilt wurde, ist der Widerrufsgrund im Sinn von Art. 62 lit. b AuG erfüllt. Es kann daher offen bleiben, ob die Vorinstanz den Widerrufsgrund des Art. 63 Abs. 1 lit. b AuG, der einen schwerwiegenden Verstoss gegen die öffentliche Sicherheit und Ordnung oder deren Gefährdung voraussetzt, zu Recht als erfüllt erachtet hat. Die Schulden des Beschwerdeführers im Umfang von ca. 35'000.-- sowie die übrigen Verurteilungen dürfen im Rahmen der Verhältnismässigkeitsprüfung gemäss Art. 96 Abs. 1 AuG (vgl. E. 5.2) und Art. 8 Ziff. 2 EMRK (vgl. E. 5.3) jedoch berücksichtigt werden.
5.2 Bei gegebenen Voraussetzungen rechtfertigt sich der Widerruf der Bewilligung nur, wenn die jeweils im Einzelfall vorzunehmende Interessenabwägung diese Massnahme als verhältnismässig erscheinen lässt, wobei einerseits die öffentlichen Interessen, andererseits die persönlichen Verhältnisse und der Grad der Integration der ausländischen Person zu berücksichtigen sind (vgl. Art. 96 Abs. 1 AuG).
Im Rahmen von Art. 96 Abs. 1 AuG sind namentlich die Schwere des Verschuldens, der Grad der Integration bzw. die Dauer der bisherigen Anwesenheit sowie die dem Betroffenen und seiner Familie drohenden Nachteile zu berücksichtigen (BGE 135 II 377 E. 4.3 S. 381).
5.3 Die Notwendigkeit einer Verhältnismässigkeitsprüfung ergibt sich zudem aus dem Anspruch auf Achtung des Familienlebens gemäss Art. 8 Ziff. 1 EMRK. Hat eine ausländische Person nahe Angehörige in der Schweiz und wird die Beziehung zu diesen tatsächlich gelebt, kann sie sich auf Art. 8 Ziff. 1 EMRK berufen, um sich der drohenden Trennung von ihren Familienangehörigen zu widersetzen (vgl. BGE 130 II 281 E. 3.1 S. 285). Die Ehe des Beschwerdeführers, welcher seit der Heirat am 26. August 2011 mit seiner in der Schweiz niedergelassenen serbischen Gattin zusammen lebt, steht somit grundsätzlich unter dem Schutz von Art. 8 Ziff. 1 EMRK.
Der Beschwerdeführer beruft sich auch auf Art. 8 Ziff 1 EMRK mit dem Hinweis, seine Eltern und zwei Geschwister würden in der Schweiz leben. Nach der Rechtsprechung schützt Art. 8 Ziff. 1 EMRK im Zusammenhang mit der Bewilligung des Aufenthalts in erster Linie die Kernfamilie, d.h. die Gemeinschaft der Ehegatten mit ihren minderjährigen Kindern (BGE 135 I 143 E. 1.3.2 S. 146). Zwar werden neben der eigentlichen Kernfamilie auch weitere familiäre Verhältnisse erfasst, sofern eine genügend nahe, echte und tatsächlich gelebte Beziehung besteht (BGE 135 I 143 E. 3.1 S. 148). Der Beschwerdeführer legt jedoch nicht dar, dass dies bei ihm der Fall wäre. Der Kontakt zu seinen Eltern und Geschwistern, den er auch besuchsweise oder mit Hilfe von Medien pflegen könnte, fällt nicht in den Schutzbereich von Art. 8 Ziff. 1 EMRK.
5.3.1 Der Anspruch auf Achtung des Familienlebens im Sinn von Art. 8 Ziff. 1 EMRK gilt nicht absolut. Gemäss Art. 8 Ziff. 2 EMRK ist ein Eingriff in das durch Ziff. 1 geschützte Rechtsgut statthaft, soweit er gesetzlich vorgesehen und in einer demokratischen Gesellschaft für die nationale oder öffentliche Sicherheit, für das wirtschaftliche Wohl des Landes, zur Aufrechterhaltung der Ordnung, zur Verhütung von Straftaten, zum Schutz der Gesundheit oder der Moral oder zum Schutz der Rechte und Freiheiten anderer notwendig ist. Analoge Voraussetzungen ergeben sich aus Art. 36 BV im Hinblick auf einen Eingriff in Art. 13 BV (BGE 135 I 143 E. 2.1 S. 147).
5.3.2 Bei der Interessenabwägung im Rahmen von Art. 8 Ziff. 2 EMRK sind 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. Zudem sind die Dauer einer allfälligen ehelichen Beziehung und weitere Gesichtspunkte relevant, welche Rückschlüsse auf deren Intensität zulassen (Geburt und Alter allfälliger Kinder; Kenntnis der Tatsache, dass die Beziehung wegen der Straftat unter Umständen nicht in der Schweiz gelebt werden kann). Von Bedeutung sind auch die Nachteile, welche dem Ehepartner oder den Kindern erwachsen würden, müssten sie dem Betroffenen in dessen Heimatstaat folgen (Urteil 2C_679/2011 vom 21. Februar 2012 E. 3.2 mit Hinweisen). Zu beachten ist schliesslich die Qualität der sozialen, kulturellen und familiären Beziehungen zum Gast- bzw. zum Heimatland (Urteil 2C_711/2011 vom 27. März 2012 E. 4.2 mit Hinweisen).
5.3.3 Je länger eine ausländische Person in der Schweiz gelebt hat, desto strengere Anforderungen sind an Entfernungs- und Fernhaltemassnahmen zu stellen. Solche sind zwar selbst bei ausländischen Personen der "zweiten Generation", die in der Schweiz geboren sind und hier ihr ganzes bisheriges Leben verbracht haben, bei Gewaltdelikten bzw. wiederholter schwerer Straffälligkeit nicht generell ausgeschlossen (BGE 135 II 110 E. 2.1 S. 112). Ähnliches gilt, falls es sich beim Betroffenen zwar nicht um einen Ausländer der "zweiten Generation" im eigentlichen Sinn handelt, aber doch um eine Person, die bereits ausgesprochen lange hier lebt (vgl. BGE 125 II 521 E. 2b S. 523 f.). Solche Ausländer dürfen in der Regel ebenfalls nicht schon wegen eines einzelnen Delikts weggewiesen werden, sondern nur bei wiederholten Straftaten von einigem Gewicht, insbesondere wenn die ausländische Person - statt sich zu bessern - mit der deliktischen Tätigkeit fortfährt und sich namentlich immer schwerere Straftaten zu Schulden kommen lässt (Urteil 2C_745/2008 vom 24. Februar 2009 E. 4.2 mit Hinweisen). Ausschlaggebend ist die Verhältnismässigkeit der Massnahme im Einzelfall, die praxisgemäss gestützt auf die gesamten wesentlichen Umstände geprüft werden muss (BGE 135 II 110 E. 2.1 S. 112).
6. Der Beschwerdeführer macht geltend, der Widerruf der Niederlassungsbewilligung sei unverhältnismässig.
6.1 Entgegen der Ansicht der Vorinstanz sei er von strafrechtlichen Massnahmen nicht unbeeindruckt geblieben. Seit der Entlassung aus dem Strafvollzug am 24. Januar 2010 habe er sich ausser eines Verkehrsregeldelikts nichts mehr zuschulden kommen lassen. Seine Straftaten seien unter dem Blickwinkel der jugendlichen Delinquenz zu betrachten, auch wenn sie noch im jungen Erwachsenenalter erfolgt seien. Damit seien analoge Umstände wie im Urteil des EGMR Emre gegen Schweiz vom 11. Oktober 2011 (5056/10) gegeben mit der Folge, dass die Wegweisung unverhältnismässig sei.
6.2 Aus dem Führungsbericht der Strafanstalt Realta vom 23. November 2009 gehe hervor, dass er - der Beschwerdeführer - sich während des Strafvollzugs tadellos verhalten und zu keinen Klagen Anlass gegeben habe. Es sei eindeutig eine Verbesserung des Verhaltens eingetreten.
6.3 Er spreche Schweizerdeutsch und sei gut integriert; nach der Entlassung aus dem Strafvollzug habe er wieder eine Anstellung gefunden und komme für seinen Lebensunterhalt selbst auf. Alle seine Familienangehörigen würden in der Schweiz leben. Seit dem Tod eines Onkels vor ungefähr vier Jahren habe er keine nahen Verwandten mehr in Mazedonien. Er und seine Familie seien türkische Mazedonier; sie sprächen Türkisch, nicht Mazedonisch. Da er keine Schule in Mazedonien besucht habe, spreche er weder Mazedonisch noch beherrsche er die kyrillische Schrift. Er habe sämtliche familiären, kulturellen, sozialen und beruflichen Kontakte in der Schweiz. Mit seinem Heimatland Mazedonien verbinde ihn nichts, nicht einmal die Sprache.
6.4 Eine Wiedereingliederung in Mazedonien sei für ihn ausgeschlossen, da er die Landessprache nicht spreche. Zwar mache die türkische Minderheit in Mazedonien ca. 3.8% aus; diese lebe jedoch im ganzen Land verteilt. Es gebe keine Gebiete, in denen ausschliesslich Türkisch gesprochen werde. Lediglich in zwei Gemeinden sei Türkisch als Amtssprache anerkannt. Da er die mazedonische Sprache weder in Wort noch Schrift verstehe und keine Schule in Mazedonien besucht habe, sei es für ihn angesichts der hohen Arbeitslosigkeit unmöglich, Arbeit zu finden.
6.5 Seiner Ehefrau, die weder Türkisch noch Mazedonisch verstehe, sei es nicht zuzumuten, ihm nach Mazedonien zu folgen. Sie sei im Alter von acht Jahren in die Schweiz gekommen und spreche weder Mazedonisch noch Türkisch. Die Rechtsprechung des Bundesgerichts, wonach es entscheidend sei, dass die Gattin bei der Eheschliessung gewusst habe, dass die Ehe wahrscheinlich nicht in der Schweiz gelebt werden könne, finde daher keine analoge Anwendung.
7. 7.1 Der Beschwerdeführer war im Alter von knapp sechs Jahren in die Schweiz eingereist. Er hat demnach den grössten Teil seines Lebens hier verbracht; im Zeitpunkt des angefochtenen Entscheids betrug seine Anwesenheitsdauer in der Schweiz fast 21 Jahre. Dieser Umstand spricht für den Verbleib in der Schweiz, ebenso die Tatsache, dass der Beschwerdeführer beruflich integriert zu sein scheint.
7.2 Was die soziale Integration betrifft, sind keine Anhaltspunkte vorhanden, welche auf eine überdurchschnittliche Eingliederung in schweizerische Verhältnisse schliessen liessen. Zwar kann der Erwägung der Vorinstanz, wonach die serbische Staatsangehörigkeit der Ehefrau des Beschwerdeführers eine echte Integration auch künftig nicht erleichtern werde, nicht gefolgt werden: Gemäss dem Wortlaut von Art. 96 Abs. 1 AuG, wonach die Behörden bei der Ermessensausübung den Grad der Integration berücksichtigen, ist die Integration nicht prospektiv, sondern retrospektiv zu beurteilen. Aus der mehrjährigen Delinquenz des Beschwerdeführers ergibt sich jedoch, dass er keine erfolgreiche soziale Integration darzutun vermag.
7.3 Eine Übersiedlung nach Mazedonien wäre für den Beschwerdeführer mit Schwierigkeiten verbunden: Er hat dort keine nahen Verwandten, die ihm den Neubeginn erleichtern könnten, und müsste wohl die mazedonische Sprache erlernen, um sich voll einzugliedern. Der Beschwerdeführer macht zu Recht geltend, dass in Mazedonien alle Schüler nichtmazedonischer Volksgruppenzugehörigkeit parallel zu ihrer Muttersprache zusätzlich die mazedonische Sprache erlernen (vgl. SILVANA SIMOSKA, Sprachpolitik[en] und Sprachenpolitik[en] in Makedonien, in: Gabriella Schubert, Makedonien. Prägungen und Perspektiven, 2005, S. 135). Das Erlernen dieser Sprache erscheint jedoch mit Blick auf das junge Alter des Beschwerdeführers zumutbar. Dessen Zugehörigkeit zur türkischsprachigen Minderheit in Mazedonien stellt demnach kein unüberwindliches Hindernis für die Rückkehr dar.
7.4 Der Beschwerdeführer ist seit dem 26. August 2011 verheiratet. Aufgrund der serbischen Staatsangehörigkeit seiner Ehefrau und ihrer ebenfalls langjährigen Anwesenheit in der Schweiz ist - auch mit Blick auf die Schwangerschaft - davon auszugehen, dass ihr eine Übersiedlung nach Mazedonien nur schwer zumutbar wäre. Der Beschwerdeführer würde daher aller Wahrscheinlichkeit nach von seiner Frau getrennt. Bei der Interessenabwägung ist jedoch zu beachten, dass die Ehe des Beschwerdeführers nicht nur nach Einleitung des Widerrufsverfahrens, sondern erst nach dem Widerruf der Niederlassungsbewilligung geschlossen worden war und im Zeitpunkt des angefochtenen Entscheids gerade knapp drei Monate gedauert hatte. Die Vorinstanz weist zu Recht darauf hin, dass die Ehefrau bei der Heirat um den drohenden (definitiven) Entzug der Niederlassungsbewilligung habe wissen müssen und daher die Trennung von ihrem Mann in Kauf genommen habe. Im Gegensatz zu dem, was der Beschwerdeführer vorbringt, gilt diese Rechtsprechung (vgl. Urteil 2C_935/2010 vom 7. Juni 2011 E. 3.3 und 3.4) gerade in jenen Fällen, in denen es dem Ehegatten der ausländischen Person nicht zumutbar ist, dieser in die Heimat zu folgen. Der Beschwerdeführer kann deshalb nichts daraus ableiten, dass seiner Frau die Übersiedlung nach Mazedonien nur schwer zuzumuten ist und er somit von ihr getrennt würde. Aufgrund des bereits erfolgten, wenn auch nicht rechtskräftigen Widerrufs der Niederlassungsbewilligung im Zeitpunkt der Eheschliessung musste beiden Partnern klar sein, dass die Ehe wahrscheinlich nicht in der Schweiz würde gelebt werden können.
7.5 Den genannten privaten Interessen des Beschwerdeführers am Verbleib in der Schweiz stehen öffentliche Interessen an seiner Wegweisung gegenüber.
7.5.1 Ausgangspunkt und Massstab für die Schwere des Verschuldens und die fremdenpolizeiliche Interessenabwägung im Rahmen eines Bewilligungsentzugs gestützt auf Art. 62 lit. b AuG (Verurteilung zu einer längerfristigen Freiheitsstrafe) ist die vom Strafgericht verhängte Strafe (BGE 129 II 215 E. 3.1 S. 216). Der Beschwerdeführer wurde im Alter von knapp 21 Jahren zu einer bedingten Gefängnisstrafe von 16 Monaten verurteilt, wobei das Bezirksgericht Horgen in seinem Urteil vom 15. März 2006 das Tatverschulden als "nicht mehr leicht" bezeichnete. Das Gericht attestierte dem Beschwerdeführer sodann ein "ausgeprägtes Mass an krimineller Energie". Es ist somit von einem mittelschweren Verschulden auszugehen.
7.5.2 Der Beschwerdeführer wurde danach wiederholt straffällig. Zu seinen Gunsten fällt ins Gewicht, dass er sich seit dem im Jugendalter verübten Raub keine Gewaltdelikte mehr hat zuschulden kommen lassen: Jene Straftaten, welche zur Verurteilung zu 16 Monaten Gefängnis und damit zum Widerruf der Niederlassungsbewilligung geführt hatten, waren keine Gewaltdelikte, ebensowenig die später verübten Straftaten. Auch wenn diesem Umstand bei der Interessenabwägung wesentliche Bedeutung zukommt (Urteil 2C_18/2009 vom 7. September 2009 E. 2.3), handelt es sich bei den fraglichen Straftaten nicht - zumindest nicht ausschliesslich - um Bagatelldelikte, wie die Vorinstanz zutreffend festhält. Der Vorinstanz ist auch darin beizupflichten, dass der vorliegende Fall nicht vollständig mit dem Fall "Emre" (vgl. Urteile des EGMR Emre gegen Schweiz vom 22. Mai 2008 [42034/04] bzw. Emre gegen Schweiz vom 11. Oktober 2011 [5056/10]) vergleichbar ist, da der Beschwerdeführer zahlreiche Straftaten nach Eintritt der Mündigkeit, ja bis zum 25. Altersjahr begangen hat und im Gegensatz zum Beschwerdeführer im Fall "Emre" keine Anzeichen einer psychischen Krankheit aufwies. Die wiederholte Delinquenz des Beschwerdeführers kann nicht durch sein jugendliches Alter relativiert werden.
7.5.3 Der Beschwerdeführer kann auch nichts daraus ableiten, dass er nach der Entlassung aus der Strafanstalt Realta am 24. Januar 2010 mit Ausnahme eines Verkehrsregeldelikts nicht mehr straffällig geworden ist. Nach der Rechtsprechung kommt dem Kriterium des Zeitablaufs seit der Tatbegehung bzw. dem seitherigen Wohlverhalten bei der Beurteilung des Rückfallrisikos erhöhte Tragweite zu (Urteil 2C_18/2009 vom 7. September 2009 E. 2.3). Vorliegend wurden die Freiheitsstrafe von acht Monaten gemäss Urteil des Bezirksgerichts Horgen vom 3. Dezember 2008 sowie die Freiheitsstrafe von vier Monaten gemäss Strafbescheid der Staatsanwaltschaft St. Gallen vom 27. Januar 2009 in der Strafanstalt Realta vollzogen, weil der Beschwerdeführer seit den Verurteilungen des Jahres 2006 wieder straffällig geworden war. Bereits zwei Monate nach der Verwarnung vom 23. Oktober 2007, am 30. Dezember 2007, kam es zu mehrfacher grober Verletzung der Verkehrsregeln, Fahren in fahrunfähigem Zustand, versuchter Vereitelung von Massnahmen zur Feststellung der Fahrunfähigkeit und Übertretung des Betäubungsmittelgesetzes (vgl. Urteil des Bezirksgerichts Horgen vom 3. Dezember 2008). Weitere neun Monate später, im September 2008, beging der Beschwerdeführer mehrfachen Diebstahl, mehrfache Sachbeschädigung und mehrfachen Hausfriedensbruch (vgl. Strafbescheid der Staatsanwaltschaft des Kantons St. Gallen vom 27. Januar 2009). Schliesslich wurde der Beschwerdeführer wegen mehrfachen Diebstahls (begangen von Sommer 2008 bis März 2009), einfacher und qualifizierter Sachbeschädigung (begangen am 20. und 21. Januar 2009), mehrfachen Hausfriedensbruchs (begangen am 20. und 21. Januar 2009), Führens eines Motorfahrzeugs in fahrunfähigem Zustand (begangen am 31. Mai 2010), Entwendung zum Gebrauch (begangen am 21. Januar 2009) und mehrfacher Widerhandlung gegen das Betäubungsmittelgesetz (begangen zwischen April und Juni 2008 sowie vom 27. bis 31. Mai 2010) verurteilt (vgl. Strafbefehl der Oberstaatsanwaltschaft des Kantons Schwyz vom 31. März 2011).
7.5.4 Diese Chronik erhellt, dass der Beschwerdeführer weder aus den Jugendstrafen, noch aus den ersten beiden Verurteilungen nach Erwachsenenstrafrecht vom 15. März 2006 und 8. November 2006, noch aus der Verwarnung vom 23. Oktober 2007 Lehren gezogen hat. Die Uneinsichtigkeit des Beschwerdeführers lässt auf eine konkrete Rückfallgefahr schliessen, welche das öffentliche Interesse an seiner Fernhaltung erhöht.
7.5.5 Die Schulden des Beschwerdeführers im Umfang von knapp Fr. 35'000.-- im Zeitpunkt des angefochtenen Entscheids wirken sich ebenfalls zu seinen Ungunsten aus. Auch wenn dem Beschwerdeführer zugute zu halten ist, dass er mit der Abbezahlung der Schulden begonnen hat, vermag dieser Umstand allein die Interessenabwägung nicht entscheidwesentlich zu ändern.
7.6 Aus den vorstehenden Erwägungen ergibt sich, dass dem privaten Interesse des Beschwerdeführers am Verbleib in der Schweiz ein erhebliches ordnungs- und sicherheitspolizeiliches Interesse an seiner Wegweisung gegenübersteht. Zudem dürfen generalpräventive Gesichtspunkte bei ausländischen Personen, welche sich nicht auf das FZA (SR 0.142.112.681) berufen können, im Rahmen der Interessenabwägung berücksichtigt werden (Urteil 2C_679/2011 vom 21. Februar 2012 E. 3. 1). Die persönlichen Verhältnisse des Beschwerdeführers, insbesondere seine Anwesenheit in der Schweiz seit dem Kindesalter, seine (kurze) Ehe und die zu erwartenden Schwierigkeiten bei einer Rückkehr nach Mazedonien, vermögen das öffentliche Interesse an seiner Fernhaltung nicht aufzuwiegen. Der angefochtene Entscheid erweist sich somit als verhältnismässig im Sinn von Art. 8 Ziff. 2 EMRK und Art. 96 AuG.
8. Nach dem Gesagten ist die Beschwerde abzuweisen, soweit darauf einzutreten ist.
Dem Verfahrensausgang entsprechend sind dem Beschwerdeführer die Kosten zu auferlegen (vgl. Art. 66 Abs. 1 BGG). Es ist keine Parteientschädigung zuzusprechen (vgl. Art. 68 BGG).
Demnach erkennt das Bundesgericht:
1. Die Beschwerde 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 Schwyz, Kammer III, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 28. September 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Die Gerichtsschreiberin: Genner