Sachverhalt:
A. Der aus Mazedonien stammende X._ (geb. 1977) heiratete am 27. Juli 2000 in seiner Heimat die Schweizer Bürgerin Y._ (mit Wohnsitz im Kanton Luzern, geb. 1976) und erhielt gestützt auf diese Eheschliessung von der Fremdenpolizei des Kantons Luzern (heute: Migrationsamt) eine Aufenthaltsbewilligung, welche in der Folge regelmässig verlängert wurde. Nachdem X._ am 17. Mai 2005 über seinen Arbeitgeber die "Aufenthaltsbewilligung C" (recte: "Niederlassungsbewilligung") zum beabsichtigten Zusammenwohnen mit seiner Schweizer Ehegattin beantragt hatte, wurde sein Aufenthaltstitel am 19. August 2005 in eine Niederlassungsbewilligung umgewandelt. Mit Urteil des Amtsgerichts Luzern vom 7. Februar 2007 wurde die Ehe mit Y._ geschieden. Auf den 1. Mai 2007 zog X._ in den Kanton Aargau, wo er am 15. Mai 2007 ebenfalls die Niederlassungsbewilligung erhielt.
B. Am 10. Oktober 2007 heiratete X._ in Mazedonien seine Landsfrau Z._ (geb. 1980), mit der er bereits zwei voreheliche Kinder hat (A._, geb. 6. Juni 2001, und B._, geb. 3. Juni 2003). Gemäss eigenen Angaben erfuhr er von deren Existenz erst im Jahre 2003, ohne sich damals aber über die Vaterschaft sicher zu sein. Nach der Heirat mit Z._ hat er die beiden Kinder dann (am 27. Oktober 2007 bzw. am 16. März 2008) anerkannt. Am 23. April 2008 stellte er für seine neue Ehefrau und die beiden Söhne im Kanton Aargau ein Familiennachzugsgesuch.
C. In der Folge sistierte das Migrationsamt des Kantons Aargau (heute: Amt für Migration und Integration) dieses Verfahren, zog die Akten des Kantons Luzern bei, gewährte X._ am 13. Juli 2009 zu den gegenüber seiner Person beabsichtigten ausländerrechtlichen Massnahmen (Widerruf der Niederlassungsbewilligung/Wegweisung) das rechtliche Gehör und verfügte diese Massnahmen schliesslich am 22. Januar 2010. Zur Begründung führte das Amt im Wesentlichen aus, X._ habe vor der Erteilung der Niederlassungsbewilligung gewusst, dass er der Vater von A._ und B._ sei; diesen Umstand aber habe er den Behörden des Kantons Luzern verschwiegen und auch beim Wechsel in den Kanton Aargau nicht auf diese Vaterschaft hingewiesen. Dies rechtfertige den Widerruf der Niederlassungsbewilligung, zumal sich diese Massnahme auch als verhältnismässig erweise.
Eine gegen diese Verfügung erhobene Einsprache beim Migrationsamt blieb erfolglos, und mit Urteil vom 2. Februar 2012 wies das Rekursgericht im Ausländerrecht des Kantons Aargau die gegen den Einspracheentscheid vom 8. November 2010 erhobene Beschwerde ebenfalls ab.
D. Mit Eingabe vom 5. März 2012 führt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht mit den Anträgen, das letztgenannte Urteil aufzuheben und vom Widerruf der Niederlassungsbewilligung abzusehen.
Das Amt für Migration und Integration des Kantons Aargau beantragt, die Beschwerde abzuweisen. Das Rekursgericht im Ausländerrecht des Kantons Aargau schliesst ebenfalls auf Abweisung der Beschwerde, ebenso das Bundesamt für Migration.
E. Mit Eingabe vom 26. März 2012 teilte X._ dem Bundesgericht mit, er habe sich einvernehmlich von seiner Ehefrau scheiden lassen. Gleichzeitig reichte er das entsprechende Scheidungsurteil des Amtsgerichts Kumanovo vom 9. März 2012 ein.

Erwägungen:
1. 1.1 Gegen kantonal letztinstanzliche Entscheide über den Widerruf der Niederlassungsbewilligung ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig (Art. 82 lit. a, Art. 83 lit. c Ziff. 2 (e contrario) und <ref-law>; <ref-ruling> E. 1.2.1 S. 4), und der Beschwerdeführer ist zur Ergreifung dieses Rechtsmittels befugt (<ref-law>).
1.2 Mit der Beschwerde kann eine Rechtsverletzung nach Art. 95 und 96 BGG geltend gemacht werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es legt seinem Urteil die Sachverhaltsfeststellungen der Vorinstanz zugrunde (<ref-law>). Mit einer Beschwerde in öffentlich-rechtlichen Angelegenheiten können diese nur dann gerügt werden, wenn sie offensichtlich unrichtig, d.h. willkürlich sind (<ref-ruling> E. 1.2.2 S. 252; <ref-ruling> E. 7.1 S. 398) oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen. Zudem ist vom Beschwerdeführer aufzuzeigen, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>).
1.3 Das Vorbringen von neuen Tatsachen oder Beweismitteln ist nur insofern möglich, als erst der Entscheid der Vorinstanz dazu Anlass gegeben hat (<ref-law>, vgl. <ref-ruling> E. 1.5 S. 146 f.). Tatsachen oder Beweismittel, welche sich auf das vorinstanzliche Prozessthema beziehen, sich jedoch erst nach dem angefochtenen Entscheid ereigneten oder entstanden sind, können von vornherein nicht durch das angefochtene Urteil veranlasst worden sein (vgl. Urteil 2C_94/2009 vom 16. Juni 2009, E.2.2). Soweit sich der Beschwerdeführer auf solche Beweismittel beruft (es betrifft dies namentlich jene zu seiner inzwischen geschiedenen Ehe mit Z._, vgl. vorne lit. E), handelt es sich um so genannte "echte Noven", welche im bundesgerichtlichen Verfahren in jedem Fall unzulässig sind (<ref-ruling> E. 2.1 S. 344).
2. Der Beschwerdeführer rügt zunächst, die Vorinstanz habe seinen Anspruch auf rechtliches Gehör (<ref-law>) verletzt. Er trägt vor, zwar habe er mittels Rechtsvertreter seine Sicht der Dinge kundgetan, doch würde in einem solch komplexen Fall, in dem eine Ehe im Mittelpunkt stehe, dergestalt die tatsächliche Situation nur bedingt wiedergegeben.
Soweit der Beschwerdeführer damit geltend machen will, er hätte vom Rekursgericht persönlich angehört werden müssen, dringt er damit nicht durch: <ref-law> vermittelt nicht zwingend das Recht, mündlich angehört zu werden. Eine mündliche Äusserungsmöglichkeit kann zwar geboten sein wegen persönlicher Umstände, die sich nur aufgrund einer mündlichen Anhörung klären lassen (vgl. GEROLD STEINMANN, in: Kommentar BV, 2. Auflage 2008, Rz. 25 zu <ref-law>) bzw. wenn sich eine solche Anhörung für den zu fällenden Entscheid als unerlässlich erweist (<ref-ruling> E. 4 S. 469 f.). Ein solcher Fall liegt aber hier nicht vor: Der Beschwerdeführer hatte in den dem Rekursgericht vorangegangenen Verfahren regelmässig Gelegenheit, seinen Standpunkt einzubringen, und auch im Verfahren vor dem Rekursgericht wäre eine persönliche Eingabe - neben derjenigen seines Rechtsvertreters - ohne weiteres möglich gewesen.
Der Beschwerdeführer macht weiter geltend, er habe vor dem Rekursgericht "nicht mal Gelegenheit für eine schriftliche Stellungnahme" (...) "zu den Bemerkungen des Beschwerdegegners" erhalten. Damit sieht er das Prinzip der Waffengleichheit verletzt.
Auch diese Rüge ist unbegründet: Zwar trifft zu, dass der Gerichtspräsident nach Eingang der Eingabe des Migrationsamtes vom 22. Dezember 2010 jene dem Beschwerdeführer "zur Kenntnisnahme" zugestellt und dabei den Schriftenwechsel als abgeschlossen erklärt hat (Verfügung vom 23. Dezember 2010, Ziff. 1 und 2). Dadurch wurde das Recht des Beschwerdeführers, von jeder beim Gericht eingegangenen Stellungnahme Kenntnis zu nehmen und sich dazu äussern zu können ("Replikrecht", dazu ausführlich <ref-ruling>) aber nicht verletzt: Das Migrationsamt hatte vor dem Rekursgericht gar nicht materiell Stellung genommen, sondern einzig unter Hinweis auf die Ausführungen im angefochtenen Einspracheentscheid Abweisung der Beschwerde beantragt. Es bestand daher kein Anlass, den Beschwerdeführer dazu noch anzuhören. Zudem hat dieser sich ohnehin auch durch den von der Vorinstanz verfügten Abschluss des Schriftenwechsels nicht davon abhalten lassen, nachträglich noch Unterlagen einzureichen. Sodann wurde er vom Rekursgericht über den Aktenbeizug aus dem Kanton Luzern orientiert und hätte ohne weiteres die Möglichkeit gehabt, Akteneinsicht zu verlangen.
<ref-law> erscheint nach dem Gesagten in keinem seiner Teilgehalte verletzt.
3. 3.1 Nach dem hier anwendbaren Bundesgesetz vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20; vgl. nicht publizierte E. 1 von <ref-ruling> mit Hinweisen) kann die Niederlassungsbewilligung widerrufen werden, wenn der Ausländer oder sein Vertreter im Bewilligungsverfahren falsche Angaben macht oder wesentliche Tatsachen verschwiegen hat (Art. 63 Abs. 1 lit. a in Verbindung mit Art. 62 lit. a AuG). Die unter dem alten Recht (Art. 9 Abs. 2 lit. a und Abs. 4 lit. a ANAG) zu diesem Widerrufsgrund entwickelte Praxis gilt im Wesentlichen auch für Art. 62 lit. a AuG. 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. 13 f ANAG bzw. Art. 90 AuG). Wesentlich sind dabei 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). Als wesentlicher Umstand gilt gemäss ständiger Rechtsprechung insbesondere das Vorhandensein von vor- bzw. ausserehelichen Kindern bei Gesuchen zum Verbleib beim in der Schweiz ansässigen Ehepartner bzw. bei der Ehepartnerin (vgl. die Urteile 2C_595/2011 vom 24. Januar 2012, E. 3.4, 2C_243/2008 vom 18. Juni 2008 E. 2.3; 2A.423/2006 vom 26. Oktober 2006 E. 2.1; 2A.346/2004 vom 10. Dezember 2004 E. 2.2, in: Pra 2005 Nr. 100 S. 716; je mit Hinweisen). Das Fehlen konkreter Fragen entbindet den Antragsteller nicht von vornherein, über wesentliche Tatsachen von sich aus zu informieren: Wie das Bundesgericht kürzlich festgehalten hat, liegt ein "Verschweigen" im Sinne von Art. 62 lit. a AuG jedenfalls dann vor, wenn der Ausländer aufgrund seiner Gesuchsbegründung bzw. anderer von ihm zu vertretender Umstände bei den Behörden einen falschen Anschein über eine wesentliche Tatsache erweckt bzw. aufrechterhält und insofern eine Täuschungshandlung begeht. Ergibt sich demgegenüber aus den konkreten Umständen des Einzelfalls, dass die Bewilligungsvoraussetzungen genauerer Abklärung bedürfen, so obliegt es kraft des im Verwaltungsverfahren geltenden Untersuchungsgrundsatzes in erster Linie den Behörden, entsprechende Fragen an den Ausländer zu richten (Urteile 2C_595/2011 vom 24. Januar 2012, E. 3.4, und 2C_403/2011 vom 2. Dezember 2011 E. 3.3.3).
3.2 Das Rekursgericht hat festgestellt, der Beschwerdeführer habe jedenfalls seit 2003/2004 um die Existenz der Kinder gewusst bzw. sei seit damals - wie er dies ursprünglich auch selber habe ausführen lassen - von seiner leiblichen Vaterschaft ausgegangen (angefochtener Entscheid E. 3.3.3 S. 10). Der Einwand, er sei sich damals - und auch bei der späteren Anerkennung der Kinder (2007/2008) - über die Vaterschaft nicht "zu 100 % sicher" gewesen, lässt diese Feststellungen des Rekursgerichts nicht als offensichtlich unrichtig erscheinen, zumal im Falle ernsthafter Zweifel an der Vaterschaft kein Grund für den Beschwerdeführer bestanden hätte, A._ und B._ als eigene Söhne zu anerkennen bzw. bereits früher mit der Mutter der Kinder zu vereinbaren, dass "er sich nicht um diese kümmern muss" (Beschwerde S. 6). Die vom Beschwerdeführer ins Feld geführten Zweifel an der Vaterschaft bleiben im Übrigen unbelegt und sind angesichts der Anerkennung der beiden Söhne letztlich auch unerheblich.
Der aus dem - nach dem Gesagten für das Bundesgericht verbindlich (<ref-law>) festgestellten - Sachverhalt gezogene Schluss des Rekursgerichts, der Beschwerdeführer habe den objektiven Tatbestand des Verschweigens wesentlicher Tatsachen im Sinne von Art. 63 Abs. 1 lit. a in Verbindung mit Art. 62 lit. a AuG erfüllt, erscheint daher nicht bundesrechtswidrig.
3.3 Was den massgebenden Zeitpunkt betrifft, geht die Vorinstanz davon aus, der Beschwerdeführer habe die Existenz ausserehelicher Kinder beim Kantonswechsel verschwiegen (angefochtener Entscheid E. 3.3, am Ende). Dies ist zu präzisieren: Beim Wechsel in den Kanton Aargau war der Beschwerdeführer bereits geschieden (vgl. vorne lit. A), und insoweit wurden die dortigen Behörden über das Bestehen einer Ehe nicht getäuscht. Anspruch auf Kantonswechsel haben Personen mit Niederlassungsbewilligung aber nur, wenn keine Widerrufsgründe nach Art. 63 AuG vorliegen (vgl. Art. 37 Abs. 3 AuG); und ein solcher war hier gegeben (vgl. vorne E. 3.2). Wesentlich ist, dass der Beschwerdeführer bereits bei der Erteilung der Niederlassungsbewilligung im Kanton Luzern nicht auf die Existenz der Kinder hingewiesen hat: Damals bildete die Ehe mit seiner Schweizer Gattin und das beabsichtigte Zusammenwohnen mit jener die rechtliche Grundlage der genannten Bewilligung (vgl. Art. 43 Abs. 2 AuG). Für die Behörden bestand aufgrund der konkreten Umstände kein erkennbarer Anlass, am anspruchsbegründenden Verhältnis zu zweifeln. Hingegen hätte die Kenntnis über die Tatsache, dass der Beschwerdeführer zwei voreheliche Kinder hat, zumindest Zweifel erweckt und Anlass zu vertieften Abklärungen gegeben. Es wäre somit Sache des Beschwerdeführers gewesen, die Ausländerbehörden von sich aus über die wahren familiären Verhältnisse zu informieren. Dies gilt umso mehr, als es sich dabei um Umstände handelte, die der Beschwerdeführer besser kannte als die Behörden und welche diese ohne seine Mitwirkung gar nicht oder nicht mit vernünftigem Aufwand ermitteln konnten (Urteil 2C_244/2010 vom 15. November 2010 E. 2.2 mit Hinweisen). Indem die Niederlassungsbewilligung auf dieser Grundlage (Ehe mit Schweizer Bürgerin, gemeinsames Zusammenwohnen) beantragt wurde, ohne dass zugleich auf die Geburt der zwei Kinder aus einer anderen Beziehung hingewiesen worden wäre, wurde ein falscher Anschein über die familiäre Situation erweckt, den der Beschwerdeführer von sich aus hätte korrigieren müssen (vorne E. 3.1). Hätte er auf die beiden Kinder hingewiesen, wäre ihm im Kanton Luzern die Niederlassungsbewilligung wohl nicht erteilt worden und damit später auch nicht diejenige im Kanton Aargau.
3.4 Der Widerruf einer Niederlassungsbewilligung ist allerdings nur zulässig, wenn er aufgrund der relevanten Gesamtumstände verhältnismässig ist (vgl. [statt vieler] Urteil 2C_656/2011 vom 8. Mai 2012, E. 2.1).
Das Rekursgericht hat hierzu erwogen, der Beschwerdeführer sei erst im Alter von rund 22 Jahren in die Schweiz übersiedelt und die heutige Ehefrau stamme aus seinem Heimatland. Zwar sei auch in beruflicher Hinsicht (seit 2007 Anstellung in einer Sicherheitsfirma) von einer "guten Integration" in der Schweiz auszugehen, doch könne der Beschwerdeführer seine hier erworbenen beruflichen Erfahrungen auch im Heimatland verwerten; die dortigen Gepflogenheiten seien ihm zweifellos noch bestens vertraut. Anzumerken bleibe, dass ein Grossteil seines Aufenthalts in der Schweiz - rund elf Jahre - wohl darauf zurückzuführen sei, dass er die Behörden nicht über seine familiäre Situation informiert habe. Dass der Widerruf der Niederlassungsbewilligung zu einer unzumutbaren Entwurzelung des Beschwerdeführers führen könnte, sei jedenfalls nicht ersichtlich.
Der Beschwerdeführer bringt nichts vor, was diese Erwägungen als bundesrechtswidrig erscheinen lassen könnte. Dass er im Mai 2011 - nach bereits verfügtem Widerruf der Niederlassungsbewilligung - noch einen Privatkredit von Fr. 52'000.-- aufgenommen hat, den er nun vom Heimatland aus allenfalls unter erschwerten Bedingungen zurückzahlen muss (S. 8 der Beschwerdeschrift), macht die verfügte ausländerrechtliche Massnahme jedenfalls nicht unverhältnismässig. Ausschlaggebend bei dieser Prüfung ist, dass die Familie des Beschwerdeführers in der Heimat lebt und er deshalb offensichtlich über enge Beziehungen dorthin verfügt. Eine Rückkehr ist ihm zuzumuten.
4. Dies führt zur Abweisung der Beschwerde.
Dem Ausgang des Verfahrens entsprechend hat der Beschwerdeführer die Kosten des bundesgerichtlichen Verfahrens zu tragen (Art. 65 f. BGG). Es sind keine Parteientschädigungen geschuldet (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, dem Amt für Migration und Integration des Kantons Aargau, dem Rekursgericht im Ausländerrecht des Kantons Aargau und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 3. August 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Klopfenstein