Sachverhalt:
A. Der mazedonische Staatsangehörige X._ (geb. 1978) heiratete im März 2004 in seiner Heimat die Schweizer Bürgerin Y._ (geb. 1967). Im Juli 2004 reiste er mit Visum in die Schweiz ein und erhielt noch im selben Monat eine Aufenthaltsbewilligung zum Verbleib bei der Ehefrau. Die Bewilligung wurde letztmals bis zum 4. Juli 2007 verlängert.
Mit Strafbefehl vom 15. Juni 2006 wurde X._ wegen grober und einfacher Verletzung von Verkehrsregeln - begangen am 29. September 2005 - mit 21 Tagen Gefängnis bedingt und einer Busse von Fr. 500.-- bestraft. Am 13. Februar 2007 verurteilte ihn das Bezirksgericht Zürich wegen Widerhandlung gegen das Betäubungsmittelgesetz, Diebstahls, Hausfriedensbruchs und infolge der Beherbergung von illegal anwesenden Landsleuten wegen Vergehen gegen Art. 23 Abs. 1 lin. 5 des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; BS 1 121 sowie Änderungen gemäss Fussnote zu Ziff. I des Anhangs 2 zum AuG [SR 142.20], insb. AS 1949 I 221 227) zu einer Freiheitsstrafe von zwanzig Monaten und zehn Tagen sowie zu einer Geldstrafe von 60 Tagessätzen zu Fr. 70.--, bedingt unter Ansetzung einer Probezeit von drei Jahren, als Zusatzstrafe zum Strafbefehl vom 15. Juni 2006. Die Delikte waren im Zeitraum zwischen Oktober 2005 und Juni 2006 begangen worden.
Wegen dieser Verurteilungen lehnte das Migrationsamt des Kantons Zürich am 3. Juli 2007 die im Mai desselben Jahres beantragte Verlängerung der Aufenthaltsbewilligung von X._ ab und setzte ihm eine Frist zur Ausreise. Die dagegen im Kanton Zürich erhobenen Rechtsmittel blieben erfolglos (Entscheide des Regierungsrates vom 10. November 2010 und des Verwaltungsgerichts vom 13. April 2011).
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 30. Mai 2011 beantragt X._ dem Bundesgericht, das Urteil des Verwaltungsgerichts vom 13. April 2011 aufzuheben und seine Aufenthaltsbewilligung zu verlängern.
Mit einem dem Bundesgericht am 12. August 2011 zugegangenem Schreiben haben sich X._ und seine Ehefrau ergänzend geäussert.
Das Migrationsamt und der Regierungsrat des Kantons Zürich haben sich nicht vernehmen lassen. Das Verwaltungsgericht beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Bundesamt für Migration stellt den Antrag, die Beschwerde abzuweisen. Hiezu hat X._ innert der bis zum 24. Oktober 2011 eingeräumten Frist keine Stellungnahme mehr abgegeben.
C. Der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgericht hat der Beschwerde mit Verfügung vom 6. Juni 2011 antragsgemäss die aufschiebende Wirkung hinsichtlich der mit dem angefochtenen Urteil verbundenen Ausreiseverpflichtung zuerkannt.

Erwägungen:
1. 1.1 Da das Gesuch um Erneuerung der Aufenthaltsbewilligung am 24. Mai 2007 gestellt wurde, haben die Vorinstanzen zu Recht auf das vor dem 1. Januar 2008 geltende materielle Ausländerrecht abgestellt (vgl. Art. 126 Abs. 1 und 2 AuG). Gemäss Art. 7 Abs. 1 Satz 1 des insoweit anwendbaren ANAG (s. zu Art. 7 insb. AS 1991 1034 1043) hat der ausländische Ehegatte eines Schweizer Bürgers Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung. Da der Beschwerdeführer auch aktuell mit seiner Schweizer Ehefrau verheiratet ist, kann er sich auf diese Bestimmung berufen, weshalb die fristgerecht eingereichte Beschwerde in öffentlich-rechtlichen Angelegenheiten nach <ref-law> zulässig ist (vgl. <ref-ruling> E. 1b S. 266).
1.2 Das am 12. August 2011 beim Bundesgericht eingegangene Schreiben des Beschwerdeführers und seiner Ehefrau ist verspätet und damit aus dem Recht zu weisen. Denn es wurde nach Ablauf der Beschwerdefrist (dazu <ref-law>) versandt und erfolgte nicht als Stellungnahme auf eine Vernehmlassung der Vorinstanzen im bundesgerichtlichen Verfahren (vgl. <ref-ruling> E. 2.2 S. 21). Im Übrigen enthält dieses Schreiben keine entscheiderheblichen Elemente.
2. Der Beschwerdeführer rügt unter Hinweis auf diverse, nachfolgend zu behandelnde Gesichtspunkte, dass die Nichtverlängerung seiner Aufenthaltsbewilligung unverhältnismässig sei.
2.1 Wie erwähnt hat der Beschwerdeführer zwar gemäss Art. 7 Abs. 1 Satz 1 ANAG grundsätzlich einen Anspruch auf Erneuerung seiner Aufenthaltsbewilligung. Dieser Anspruch erlischt jedoch gemäss Art. 7 Abs. 1 Satz 3 ANAG, falls ein Ausweisungsgrund vorliegt. Die Vorinstanz beruft sich insoweit auf den Ausweisungsgrund nach Art. 10 Abs. 1 lit. a ANAG (AS 1949 I 221 227). Danach kann ein Ausländer aus der Schweiz ausgewiesen werden, wenn er wegen eines Verbrechens oder Vergehens gerichtlich bestraft wurde. Mit Blick auf die erwähnten Verurteilungen vom 15. Juni 2006 und 13. Februar 2007 ist diese Voraussetzung an sich erfüllt. Allerdings soll der Anspruch gemäss Art. 11 Abs. 3 ANAG - aber auch angesichts von Art. 8 Ziff. 2 EMRK - nur erlöschen, wenn dies nach den gesamten Umständen angemessen erscheint.
Demnach ist mittels einer Interessenabwägung jeweils im Einzelfall zu prüfen, ob die Nichtverlängerung der Bewilligung verhältnismässig ist. Hierbei sind die Schwere der begangenen Delikte, der seither vergangene Zeitraum und das dabei an den Tag gelegte Verhalten des Ausländers, die Gesamtdauer seiner Anwesenheit in der Schweiz, die Auswirkungen einer Wegweisung sowie die familiäre und berufliche Situation zu berücksichtigen. Von Bedeutung sind auch die Nachteile, welche dem Ehepartner oder allfälligen Kindern erwachsen würden, müssten sie dem Betroffenen in dessen Heimat folgen oder ohne ihn in der Schweiz verbleiben (vgl. <ref-ruling> E. 4.3 S. 381 f. mit Hinweisen; Art. 16 Abs. 3 der Vollziehungsverordnung vom 1. März 1949 zum ANAG [ANAV; AS 1949 I 228]; Urteil des Europäischen Gerichtshofs für Menschenrechte [EGMR] Boultif gegen Schweiz vom 2. August 2001, Recueil CourEDH 2001-IX S. 137 § 48).
Bei einem mit einer Schweizer Bürgerin verheirateten Ausländer, der erstmals um eine Bewilligung oder nach bloss kurzer Aufenthaltsdauer um deren Erneuerung ersucht, ist das Bundesgericht in seiner ständigen Rechtsprechung zum ANAG davon ausgegangen, dass die Grenze, von der an in der Regel selbst dann keine Bewilligung mehr erteilt wird, wenn dem Ehepartner die Ausreise nur schwer zumutbar erscheint, bei einer Freiheitsstrafe von zwei Jahren liegt. In einer solchen Konstellation sind aussergewöhnliche Umstände vonnöten, um die Erteilung einer Aufenthaltsbewilligung dennoch zu rechtfertigen. Wie die Vorinstanz zutreffend bemerkt, handelt es sich bei den zwei Jahren allerdings nur um einen Richtwert. Bezüglich des Strafmasses ist keine feste Grenze zu ziehen (sog. Reneja-Praxis; <ref-ruling>; <ref-ruling> E. 4.4 S. 382; <ref-ruling> E. 4.1 S. 185 mit Hinweisen).
2.2 Die Vorinstanz weist darauf hin, dass bereits der Regierungsrat erwogen habe, das Verschulden könne aus fremdenpolizeilicher Sicht nicht als leicht beurteilt werden, vor allem hinsichtlich der strengen Praxis bei schweren Betäubungsmitteldelikten. Der Regierungsrat führte zudem aus, generalpräventive Überlegungen würden erst dann an Bedeutung verlieren, wenn Entfernungs- bzw. Fernhaltemassnahmen gegen den Fehlbaren einmal ergriffen, durchgesetzt und für eine der Schwere der Tat angemessene Zeitdauer aufrechterhalten wurden und sich der Betroffene zwischenzeitlich nichts mehr habe zuschulden kommen lassen. Das Verwaltungsgericht bemerkt darüber hinaus, die erfolgreiche Resozialisierung im Strafrecht sei nicht mit einer Bewährung in polizeirechtlicher Hinsicht gleichzusetzen. Als Stichworte seien insoweit insbesondere die Unfreiwilligkeit der Bewährung im Strafvollzug anzuführen. Auch wenn das Rekursverfahren beim Regierungsrat unverständlich lange gedauert habe, sei der erfolgreiche Strafvollzug zu kurz, um daraus eine Bewährung im Alltag auf Dauer ableiten zu können. Erschwerend komme hinzu, dass der Beschwerdeführer schon früher in seiner Heimat (1997 infolge Diebstahls) sowie während eines Asylverfahrens in der Schweiz (2002 mit Strafbefehl infolge Fahrens ohne gültigen Fahrausweis sowie Fälschung von Ausweisen) verurteilt worden sei.
2.3 Es trifft zu, dass das Bundesgericht bei Betäubungsmitteldelikten, durch welche zahlreiche Menschen an Leib und Leben gefährdet werden, eine strenge Praxis verfolgt (<ref-ruling> E. 4a S. 527). Es soll prinzipiell unterbunden werden, dass einschlägig vorbestrafte Ausländer erneut im Inland mit Drogen handeln können. Wie der Beschwerdeführer richtig bemerkt, würdigen die Vorinstanzen vorliegend jedoch nicht oder nicht genügend, dass der Beschwerdeführer nicht wegen Teilnahme am Drogenhandel im "klassischen" Sinne verurteilt wurde. Der Beschwerdeführer hatte einen Rucksack von einem Landsmann zur Aufbewahrung entgegengenommen, ohne zunächst zu wissen, was sich darin befand. Erst kurze Zeit später erkannte er, dass der Rucksack Drogen enthielt. Ihm wurde zur Last gelegt, danach nicht die Polizei kontaktiert oder die Drogen vernichtet zu haben. Statt dessen rief er seinen Landsmann, dessen Telefon von der Polizei abgehört wurde, an und teilte ihm mit, er möge den Rucksack umgehend wieder abholen, er wolle nichts damit zu tun haben (s. dem Strafurteil angehängte Anklageschrift der Staatsanwaltschaft vom 5. Dezember 2006). Daraus ist zu entnehmen, dass der Beschwerdeführer nicht zu dem Täterkreis zu rechnen ist, der mit Drogen handeln bzw. sich dadurch bereichern will. Das Strafgericht wertete das Verschulden des Beschwerdeführers in Bezug auf das Betäubungsmitteldelikt trotz der hohen Drogenmenge denn auch als "eher leicht" (s. S. 11 f. des Protokolls der Strafverhandlung vom 13. Februar 2007). Insgesamt meinte es, dass die vom Juli 2006 bis zur Strafverhandlung erstandene (Untersuchungs-)Haft den Beschwerdeführer genügend beeindruckt habe, um künftig nicht mehr straffällig zu werden. Daher sah es im Urteil vom 13. Februar 2007 von einer unbedingten Strafe ab und bestimmte die Probezeit auf drei Jahre.
2.4 Immerhin bemerken die Vorinstanzen mit Blick auf die erwähnte Reneja-Praxis aber richtig, dass bei Freiheitsstrafen von insgesamt rund 21 Monaten ein "gewichtiger Ausgangspunkt" für eine Fernhaltung des Beschwerdeführers gegeben ist.
Die Verweigerung des weiteren Aufenthalts setzt nicht in jedem Fall voraus, dass vor Begehung der letzten Straftat eine fremdenpolizeiliche Verwarnung ergangen ist (Urteile des Bundesgerichts 2C_283/ 2011 vom 30. Juli 2011 E. 2.3 und 2C_319/2008 vom 10. Juni 2008 E. 2 in fine; je mit Hinweisen). Allerdings kann das Fehlen einer Verwarnung in der Interessenabwägung zugunsten des Ausländers gewertet werden. Genauso wäre aber umgekehrt zu dessen Lasten zu berücksichtigen, dass er trotz Verwarnung weitere Delikte begeht. Vorliegend ist der Beschwerdeführer zwar bereits wegen des Strafbefehls vom 15. Juni 2006 ausländerrechtlich verwarnt worden. In zeitlicher Hinsicht beging er danach jedoch keine Delikte mehr, auch wenn die Verurteilung vom 13. Februar 2007 erst nach der Verwarnung vom Juli 2006 erfolgte. Da die Migrationsbehörde damals von der nachfolgenden Verurteilung noch nichts wissen konnte, steht die Verwarnung dem interessierenden Entscheid über die Nichtverlängerung der Bewilligung nicht entgegen (vgl. Urteil des Bundesgerichts 2A.737/2004 vom 30. März 2005 E. 3, insb. E. 3.3, in: Pra 2006 Nr. 26 S. 184). Dennoch ist dem Beschwerdeführer zugute zu halten, dass er nach dem Strafbefehl vom Juni 2006 und der anschliessenden Verwarnung keine Delikte mehr begangen hat.
Die Vorinstanzen räumen sodann in nicht zu beanstandender Weise ein, dass die Ehe des Beschwerdeführers intakt ist und der Schweizer Ehefrau nicht zugemutet werden kann, ihrem Gatten in sein Herkunftsland nachzufolgen. Es handelt sich nach der Reneja-Praxis (s. E. 2.1 hievor) somit um einen Grenzfall.
2.5 Der Beschwerdeführer weist darauf hin, dass er nunmehr schon eine geraume Zeit in der Schweiz lebe, die letzte Straftat bereits mehrere Jahre zurückliege und das Verfahren beim Regierungsrat besonders lange gedauert habe. Er sei erwerbstätig, in der Schweiz sozial gut integriert und sei nie der öffentlichen Fürsorge zur Last gefallen. Die Vorinstanz geht insoweit von einer "mittleren Aufenthaltsdauer von sieben Jahren mit üblichen Integrationsleistungen ohne Auffälligkeiten" aus.
Aus einer Rechtsverzögerung als solcher ergibt sich kein Anspruch auf Erteilung oder Erneuerung der beantragten ausländerrechtlichen Bewilligung (vgl. Urteile des Bundesgerichts 2A.414/2001 vom 5. Februar 2002 E. 5b/bb; 2C_757/2009 vom 6. Mai 2010 E. 6). Auch war dem Beschwerdeführer und seiner Ehefrau relativ bald nach der letzten strafrechtlichen Verurteilung vom Februar 2007 klar, dass das Migrationsamt die Aufenthaltsbewilligung nicht zu verlängern beabsichtigte. Dieses verfügte nach Anhörung des Beschwerdeführers Anfang Juli 2007 die Nichtverlängerung.
Allerdings dauerte das Rechtsmittelverfahren im Kanton anschliessend insgesamt drei Jahre und neun Monate. Allein auf das Rekursverfahren beim Regierungsrat entfielen über drei Jahre und drei Monate. Dabei wurde diese Verzögerung nicht vom Beschwerdeführer verursacht. Dieser und seine Ehefrau fragten vielmehr mehrfach vergeblich nach, ob bald mit einem Entscheid gerechnet werden könne. Der Regierungsrat bat gelegentlich um neue Auskünfte über die aktuelle Situation des Beschwerdeführers. Dessen Vorgehensweise liess den Eindruck aufkommen, dass er zuwarten wolle, ob sich der Beschwerdeführer in der Zwischenzeit bewährt. Obwohl dies der Fall war - namentlich verstrich die vom Strafgericht verfügte dreijährige Probezeit ohne negative Vorkommnisse und der Beschwerdeführer ging einer Arbeit nach -, erklärten die Vorinstanzen schliesslich, dass das öffentliche Interesse an der Entfernung des Beschwerdeführers trotzdem die privaten Interessen an seinem Verbleib überwiege. Insoweit wäre es aber nicht nötig gewesen, derart lange mit dem Rekursentscheid zuzuwarten. Wenn zudem eine fortbestehende ernsthafte Gefahr für die öffentliche Sicherheit und Ordnung befürchtet wird, ist es erstaunlich, dass während einer so langen Zeit, in welcher sich die betreffende Person auf freiem Fuss befindet, kein Entscheid gefällt wird. Im Zeitpunkt des Urteils des Verwaltungsgerichts waren denn auch schliesslich fünfeinhalb Jahre seit dem Betäubungsmitteldelikt und rund fünf Jahre seit der letzten Straftat - dem Diebstahl einer Stereoanlage aus einem Fahrzeug - vergangen. Seither ist der Beschwerdeführer strafrechtlich nicht mehr in Erscheinung getreten. Auch wurde dem Beschwerdeführer nicht vorgeworfen, Sozialhilfe bezogen oder seit den Verurteilungen gezeigt zu haben, dass er nicht gewillt oder fähig ist, sich in die in der Schweiz geltende Ordnung einzufügen (vgl. Art. 10 Abs. 1 lit. b und d ANAG sowie Art. 16 Abs. 2 ANAV).
2.6 In Anbetracht der Gesamtumstände erweist sich die Verweigerung der Erneuerung der Aufenthaltsbewilligung als unverhältnismässig (vgl. erwähntes Urteil Boultif gegen Schweiz §§ 46 ff.). Dies vor allem deshalb, weil die Ehe mit der Schweizer Bürgerin intakt ist und es sich vorliegend ursprünglich um einen Grenzfall nach der Reneja-Praxis handelte, wobei der Regierungsrat dann - wie dargelegt - zu lange mit seinem Entscheid zugewartet und der Beschwerdeführer seit der fremdenpolizeilichen Verwarnung keine Straftaten mehr begangen hat. Hierbei sei jedoch nochmals betont, dass die lange Verfahrensdauer als solche keinen Anspruch auf Erneuerung der Bewilligung einräumt. Zudem könnte der Beschwerdeführer bei erneuter Delinquenz oder bei Trennung von seiner Ehefrau möglicherweise nicht mehr mit einer Verlängerung seiner Bewilligung bzw. einem Verbleib in der Schweiz rechnen. Dies hat der Beschwerdeführer als Androhung von Massnahmen im Sinne von Art. 16 Abs. 3 Satz 2 ANAV bzw. Art. 96 Abs. 2 AuG zu verstehen.
2.7 Nach dem Dargelegten kann offen gelassen werden, ob die Vorinstanzen mit Blick auf die Absicht des Gesetzgebers, Schweizer mit ausländischen Familienangehörigen grundsätzlich gleich zu behandeln wie EU-Bürger (vgl. Botschaft vom 8. März 2002 zum AuG, BBl 2002 3792 zu Art. 41 E-AuG), überhaupt - wie hier geschehen - generalpräventive Motive anrufen oder ob sie sich bloss auf das persönliche Verhalten des Beschwerdeführers stützen durften (vgl. dazu Näheres in BGE <ref-ruling> E. 3.4.1 S. 182 ff. mit Hinweisen). Zu dieser Problematik haben sich die Vorinstanzen nicht geäussert, obwohl sie hierauf bereits namentlich in einem Urteil des Bundesgerichts vom 1. März 2010 (2C_541/2009 E. 3.3) hingewiesen worden waren.
2.8 Mithin hat der Beschwerdeführer weiterhin einen Anspruch nach Art. 7 ANAG auf Erneuerung der Aufenthaltsbewilligung. Daher ist der anders lautende Entscheid des Verwaltungsgerichts in Gutheissung der Beschwerde aufzuheben und das kantonale Migrationsamt zur Erneuerung der Aufenthaltsbewilligung anzuweisen.
3. Bei diesem Ausgang des Verfahrens sind keine Kosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Hingegen hat der Kanton Zürich den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (<ref-law>). Über die Kosten- und Entschädigungsfolgen in den vorinstanzlichen Verfahren hat das Verwaltungsgericht neu zu entscheiden (vgl. Art. 67 und 68 Abs. 5 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, das Urteil des Verwaltungsgerichts des Kantons Zürich vom 13. April 2011 aufgehoben und das Migrationsamt des Kantons Zürich angewiesen, dem Beschwerdeführer die Aufenthaltsbewilligung zu erneuern.
2. Es werden keine Gerichtskosten erhoben.
3. Der Kanton Zürich hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4. Die Sache geht an das Verwaltungsgericht des Kantons Zürich zu neuem Entscheid über die Kosten- und Entschädigungsfolgen in den vorinstanzlichen Verfahren.
5. Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zürich, 2. Kammer, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 24. November 2011
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Merz