Erwägungen:
1. 1.1 Der mazedonische Staatsangehörige X._ (geb. 1974) reiste im September 2003 von Deutschland kommend ohne Bewilligung in die Schweiz ein. Zwei Monate später heiratete er die Schweizer Bürgerin Y._ (geb. 1974), worauf er eine - letztmals bis zum 12. November 2008 verlängerte - Aufenthaltsbewilligung zum Verbleib bei der Ehefrau erhielt. Mit Verfügung vom 23. September 2009 lehnte die Sicherheitsdirektion (Migrationsamt) des Kantons Zürich sowohl die Erneuerung der Aufenthaltsbewilligung als auch die Erteilung der beantragten Niederlassungsbewilligung ab. Zur Begründung führte sie im Wesentlichen aus, X._ habe mit der Schweizer Bürgerin eine Scheinehe abgeschlossen, um die ausländerrechtlichen Vorschriften zu umgehen. Die Ehe wurde am 12. September 2007 rechtskräftig geschieden. Die von ihm im Kanton erhobenen Rechtsmittel wurden vom Regierungsrat und anschliessend vom Verwaltungsgericht des Kantons Zürich abgewiesen.
1.2 Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 14. Juni 2011 beantragt X._ dem Bundesgericht, es sei das im Kanton zuletzt ergangene Urteil des Verwaltungsgerichts vom 13. April 2011 aufzuheben und dieses bzw. die Sicherheitsdirektion anzuweisen, ihm die Niederlassungsbewilligung zu erteilen. Eventualiter sei die Aufenthaltsbewilligung zu verlängern und die Frage der vorzeitigen Erteilung der Niederlassungsbewilligung zu prüfen.
Die Sicherheitsdirektion und der Regierungsrat des Kantons Zürich haben sich nicht vernehmen lassen. Das Verwaltungsgericht stellt den Antrag, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Das Bundesamt für Migration beantragt - mit Postaufgabe vom 18. Oktober 2011 und deshalb verspätet und unbeachtlich - die Abweisung der Beschwerde.
1.3 Der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts hat der Beschwerde hinsichtlich der Ausreiseverpflichtung mit Verfügung vom 22. Juni 2011 antragsgemäss die aufschiebende Wirkung zuerkannt.
2. 2.1 Der Regierungsrat und das Verwaltungsgericht lassen offen, ob der Beschwerdeführer im November 2003 eine sog. Ausländerrechts- oder Scheinehe mit der Schweizer Bürgerin eingegangen ist. Sie kommen indes zum Schluss, der Beschwerdeführer habe sich weniger als drei Jahre nach Eheschliessung (vgl. Art. 50 Abs. 1 lit. a AuG [SR 142.20]) rechtsmissbräuchlich auf die Ehe berufen, um seinen weiteren Aufenthalt in der Schweiz zu ermöglichen. Sie führen hiefür zahlreiche Indizien an. Insbesondere habe der Beschwerdeführer mit einer Landsfrau in Mazedonien zwei Kinder gezeugt, die im Juli 2005 und Juli 2007 geboren seien. Daher habe er gemäss Art. 51 Abs. 1 lit. a AuG keinen Anspruch auf die begehrten ausländerrechtlichen Bewilligungen. Ebenso wenig lägen Umstände vor, die - auch nach Auflösung der Familiengemeinschaft bzw. der einvernehmlichen Scheidung der Ehe - einen weiteren Aufenthalt gestützt auf Art. 50 Abs. 1 lit. b AuG erforderlich machen.
2.2 Der Beschwerdeführer macht geltend, seine Ehefrau habe psychische Probleme gehabt. Insoweit seien seine sexuellen Bedürfnisse nicht befriedigt worden. Wegen seiner "ausserehelichen Untreue in sexueller Hinsicht" könne jedoch nicht gefolgert werden, er habe sich rechtsmissbräuchlich auf die Ehe berufen. Seine frühere Schweizer Ehefrau sowie deren Eltern hätten "nur Gutes" über ihn berichtet. Unter anderem habe er Erstere anlässlich ihrer Klinikaufenthalte wiederholt besucht. Er habe immer "mit offenen Karten" gespielt und seiner Schweizer Ehefrau die Kinder nicht verschwiegen.
2.3 Es stimmt, dass der Beschwerdeführer seine Schweizer Ehefrau jeweils von der bevorstehenden Geburt der ausserehelich gezeugten Kinder unterrichtete. Auch trifft es zu, dass das Bundesgericht ausgeführt hat, einer Ehebeziehung oder einem Konkubinat sei nicht bloss deswegen die erforderliche Qualität abzuerkennen, weil die gegenseitige sexuelle Anziehung nachgelassen habe. Allerdings hat das Bundesgericht hinzugefügt, dass insoweit die konkreten Umstände des Einzelfalles zu berücksichtigen seien (Urteil 5C.135/2002 vom 2. Juli 2002 E. 2.5).
Der Beschwerdeführer kannte die psychische Instabilität seiner Ehefrau und ihre grosse Enttäuschung ob seiner ausserehelichen Beziehung, die zur Zeugung des ersten Kindes führte. Damals hatte sie sich drei bis vier Wochen von ihm getrennt und ihm hernach nur verziehen, weil er ihr erklärt hatte, es sei bloss eine "kurze Affäre" gewesen. Dennoch hatte der Beschwerdeführer danach wieder Geschlechtsverkehr, der zudem erneut ungeschützt war, mit der selben Landsfrau, was schliesslich zur Geburt des zweiten Kindes führte und der Anlass war, dass sich die Schweizer Ehefrau definitiv vom Beschwerdeführer trennte. Zwar hat der Beschwerdeführer die Kindsmutter nach seiner Scheidung nicht geheiratet oder ein Nachzugsgesuch für sie gestellt. Diese beiden Aspekte sind jedoch nicht ausschlaggebend, zumal er bisher nicht über einen gesicherten Anwesenheitstitel für die Schweiz verfügt. Bemerkenswert ist hingegen, dass der Beschwerdeführer der Kindsmutter verhältnismässig hohe Unterhaltsleistungen zukommen liess und im Sommer 2008 versuchte, sie und die Kinder besuchsweise in die Schweiz einreisen zu lassen.
Mit Blick auf die Gesamtumstände ist daher nicht zu beanstanden, dass die Vorinstanzen davon ausgehen, der Beschwerdeführer sei nach der Geburt des ersten Kindes im Juli 2005 bloss noch aus ausländerrechtlichen Gründen an der Ehe mit der Schweizer Bürgerin interessiert gewesen. Es ist unglaubwürdig, dass der Beschwerdeführer durch die Beziehung mit seiner Landsfrau nur sexuelle Bedürfnisse befriedigen wollte, er im Übrigen aber einen echten Ehewillen bzw. schützenswerte Motive für die Fortführung der Ehe mit der Schweizer Ehefrau gehabt habe. Wäre dies tatsächlich der Fall gewesen, hätte er Letztere nicht erneut mit ein und derselben Landsfrau hintergangen. Fehl geht insoweit der Einwand des Beschwerdeführers, von ihm seien keine täuschenden Machenschaften ausgegangen, weil er der Schweizer Ehefrau die bevorstehenden Geburten der Kinder mitgeteilt habe. Vielmehr hatte er ihr die Aufnahme und später die Fortführung der Beziehung mit der Landsfrau zunächst jeweils verheimlicht.
2.4 Da der Beschwerdeführer noch vor dem dreijährigen Bestehen der Ehegemeinschaft mit der Schweizer Bürgerin rechtsmissbräuchlich Aufenthaltsansprüche als Ehepartner geltend gemacht hat, scheidet eine auf Art. 50 Abs. 1 lit. a in Verbindung mit Art. 42 AuG gestützte weitere Bewilligung des Aufenthaltes gemäss Art. 51 Abs. 1 lit. a AuG aus (vgl. <ref-ruling> E. 3.1.2 S. 347). Ebenso wenig hat er einen Anspruch auf Erteilung der Niederlassungsbewilligung nach Art. 42 Abs. 3 AuG, da die Ehegemeinschaft erst recht nicht fünf Jahre bestanden hat (Urteil 2C_284/2011 vom 21. September 2011 E. 2.2 mit Hinweisen). Auch wenn der Beschwerdeführer unter anderem beruflich und sprachlich sehr gut integriert sein mag, ist noch kein wichtiger persönlicher Grund im Sinne von Art. 50 Abs. 1 lit. b AuG gegeben, der einen weiteren Aufenthalt erforderlich macht (vgl. <ref-ruling> E. 3.2 S. 348 ff.; Urteil 2C_155/2011 vom 7. Juli 2011 E. 4.7). Der Beschwerdeführer ist nur zwei Monate vor Eheschliessung in die Schweiz gelangt, berief sich - wie gezeigt - nach weniger als drei Jahren Ehe rechtsmissbräuchlich auf diese und hat den überwiegenden Teil seines Lebens in der Heimat verbracht, wohin er auch während seines Aufenthaltes in der Schweiz regelmässig zurückkehrte und wo er eine aussereheliche Beziehung führte, aus der die zwei Kinder hervorgingen. Seine soziale Wiedereingliederung ist dort nicht stark gefährdet. Dem Dargelegten zufolge kann im Übrigen offen gelassen werden, ob sich der Beschwerdeführer in intertemporaler Hinsicht überhaupt auf Art. 50 AuG berufen kann. Daran bestehen Zweifel, nachdem seine Ehe im Sommer 2007 rechtskräftig geschieden wurde, die mit Blick auf die Ehe erteilte Aufenthaltsbewilligung im November 2007, also noch vor Inkrafttreten des AuG am 1. Januar 2008 auslief, und sich die zuletzt im Juli 2008 bis zum November 2008 gewährte Bewilligungsverlängerung nicht mehr auf die Ehe stützen konnte (vgl. erwähntes Urteil 2C_284/2011 E. 2.2; Urteil 2C_365/2010 vom 22. Juni 2011 E. 3.6).
2.5 Der Beschwerdeführer beruft sich darüber hinaus auf das Verbot des widersprüchlichen Verhaltens und den Vertrauensschutz (dazu allg. <ref-ruling> E. 6.1 S. 637 mit Hinweisen). Die Behörden hätten seine Aufenthaltsbewilligung in Kenntnis sämtlicher Umstände jeweils verlängert. Sie könnten daher nicht später die Erneuerung der Aufenthaltsbewilligung beliebig verweigern.
Als das Migrationsamt die Bewilligung in den Jahren 2005 und 2006 jeweils verlängerte, konnte es noch nichts Näheres vom fehlenden Ehewillen des Beschwerdeführers wissen (s. auch E. 2.3 hievor). Dem Beschwerdeführer ist jedoch Recht zu geben, dass - entgegen der Darstellung der Vorinstanz - das Migrationsamt von der erfolgten Scheidung und dem Vorhandensein der beiden ausserehelich geborenen Kinder bereits wusste bzw. wissen musste, als es die Bewilligung im Juli 2008 letztmals bis November 2008 verlängerte. Da der Beschwerdeführer jedoch jeglichen Rechtsmissbrauch bestritt, ist nicht zu beanstanden, wenn die Vorinstanzen erst später, infolge zusätzlicher Abklärungen zur Überzeugung des Gegenteils gelangten. Die blosse Erneuerung einer Aufenthaltsbewilligung - hier zudem um bloss vier Monate - begründet für sich allein noch kein schutzwürdiges Vertrauen auf weitere Verlängerungen derselben (<ref-ruling> E. 3b S. 388). Im Übrigen macht der Beschwerdeführer vor Bundesgericht nicht geltend, was für Dispositionen er mit Blick auf das Verhalten der Behörden getroffen hatte, die er nicht mehr rückgängig machen könnte. Mithin stösst der Vorwurf der Verletzung des Vertrauensgebotes ins Leere.
2.6 Soweit der Beschwerdeführer schliesslich die vorzeitige Erteilung einer Niederlassungsbewilligung nach Art. 34 Abs. 4 AuG begehrt, ist das Bundesgericht mangels Rechtsanspruchs nicht dazu berufen, eine materielle Beurteilung vorzunehmen (vgl. <ref-law>). Der Beschwerdeführer macht im Übrigen nicht geltend, die Vorinstanzen hätten seinen diesbezüglichen Antrag nicht behandelt und seien dadurch in Rechtsverweigerung verfallen. Sowohl das Migrationsamt als auch der Regierungsrat lehnten ausdrücklich eine Bewilligungserteilung nach Art. 34 Abs. 4 AuG ab.
3. Dem Dargelegten zufolge erweist sich die Beschwerde als offensichtlich unbegründet, soweit auf sie einzutreten ist. Sie kann daher im vereinfachten Verfahren mit summarischer Begründung und unter ergänzendem Hinweis auf die Ausführungen der Vorinstanzen behandelt werden. Diesem Ausgang entsprechend hat der Beschwerdeführer die Kosten des bundesgerichtlichen Verfahrens zu tragen (Art. 65 f. BGG); Parteientschädigungen werden nicht geschuldet (<ref-law>).

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 Zürich, 2. Kammer, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 20. Dezember 2011
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Merz