Sachverhalt:
A. X._ (geb. 1979) ist Staatsangehöriger von Bangladesch und reiste erstmals im Januar 2001 in die Schweiz ein. Nach Abweisung seines Gesuchs um Asyl im Mai 2001 kehrte er vorerst in sein Heimatland zurück. Im Mai 2003 reiste er erneut in die Schweiz ein und stellte ein Asylgesuch, auf welches nicht eingetreten wurde. Im November 2003 reichte er bei der Schweizer Botschaft in Bangladesch ein weiteres Asylgesuch ein, wartete den Entscheid darüber aber nicht ab (das Gesuch wurde am 23. März 2004 abgeschrieben), sondern reiste am 31. März 2004 wiederum in die Schweiz ein, wo er ein viertes Mal um Asyl ersuchte. Am 22. September 2004 heiratete X._ die Schweizer Bürgerin Y._ (geb. 1981), worauf ihm eine Aufenthaltsbewilligung zum Verbleib bei seiner Ehefrau erteilt wurde; das Asylgesuch zog er zurück.
B. Nach Überprüfung der ehelichen Verhältnisse wies das Migrationsamt des Kantons Zürich am 18. März 2009 das Gesuch von X._ vom 25. August 2008 um Verlängerung der Aufenthaltsbewilligung ab und verweigerte ihm den weiteren Aufenthalt. Es erwog dabei im Wesentlichen, X._ und Y._ seien eine Scheinehe eingegangen. Den hiergegen erhobenen Rekurs wies der Regierungsrat des Kantons Zürich mit Beschluss vom 24. Juni 2009 ab. Dagegen wandte sich X._ erfolglos an das Verwaltungsgericht des Kantons Zürich, welches mit Urteil vom 3. Februar 2010 die Beschwerde abwies.
C. Mit Eingabe vom 5. Mai 2010 erhebt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten sowie subsidiäre Verfassungsbeschwerde an das Bundesgericht. Er beantragt die Aufhebung des Urteils des Verwaltungsgerichts vom 3. Februar 2010 sowie die Bewilligung seines weiteren Aufenthalts im Kanton Zürich (Verlängerung der Aufenthaltsbewilligung, Erteilung der Niederlassungsbewilligung). Eventualiter sei das Verfahren an die Vorinstanz zwecks Vervollständigung des Sachverhalts zurückzuweisen.
D. Das Verwaltungsgericht des Kantons Zürich sowie das Bundesamt für Migration schliessen auf Abweisung der Beschwerde, während sich der Regierungsrat und die Sicherheitsdirektion des Kantons Zürich nicht geäussert haben.
E. Mit Verfügung vom 18. Mai 2010 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt.
F. Nach Ablauf der Beschwerdefrist hat der Beschwerdeführer am 11. Oktober 2010 eine zusätzliche Eingabe eingereicht.

Erwägungen:
1. 1.1 Art. 83 lit. c Ziff. 2 BGG schliesst die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen Entscheide über ausländerrechtliche Bewilligungen aus, auf deren Erteilung weder nach dem Bundes- noch dem Völkerrecht ein Rechtsanspruch besteht.
1.2 Gemäss Art. 42 Abs. 1 des auf den 1. Januar 2008 in Kraft getretenen, hier unbestrittenermassen anwendbaren Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20) haben ausländische Ehegatten von Schweizerinnen und Schweizern Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, wenn sie mit diesen zusammenwohnen; nach einem ordnungsgemässen und ununterbrochenen Aufenthalt von fünf Jahren haben die Ehegatten Anspruch auf Erteilung der Niederlassungsbewilligung (Art. 42 Abs. 3 AuG). Der Beschwerdeführer ist mit einer Schweizer Bürgerin verheiratet. Ob er mit ihr zusammen lebt, ist zweifelhaft, kann jedoch offen bleiben. Die Frage, ob ihm die Verlängerung der Bewilligung verweigert werden durfte, weil eine Schein- oder Ausländerrechtsehe vorliegt, betrifft nicht das Eintreten, sondern bildet Gegenstand der materiellen Beurteilung (vgl. <ref-ruling> E. 1b S. 266 mit Hinweisen). Auf seine frist- und formgerecht eingereichte Beschwerde in öffentlich-rechtlichen Angelegenheiten ist grundsätzlich einzutreten.
1.3 Die Verfassungsbeschwerde ist im Verhältnis zur Beschwerde in öffentlich-rechtlichen Angelegenheiten subsidiär (Art. 113 BGG). Da hier die Letztere zur Verfügung steht, ist die vom Beschwerdeführer gleichzeitig erhobene Verfassungsbeschwerde nicht zulässig, weshalb darauf nicht eingetreten werden kann.
1.4 Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Es ist daher weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden (vgl. <ref-ruling> E. 1.4 S. 400).
Hinsichtlich der Verletzung von Grundrechten gilt indessen eine qualifizierte Rügepflicht (Art. 106 Abs. 2 BGG; vgl. <ref-ruling> E. 1.4.2 S. 254). Soweit vorliegend bloss sinngemäss eine Verletzung von Art. 8 EMRK geltend gemacht wird, kann wegen ungenügender Begründung auf die Beschwerde nicht eingetreten werden.
1.5 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (Art. 105 Abs. 1 BGG). Die Feststellung des Sachverhalts kann nur gerügt bzw. vom Bundesgericht von Amtes wegen berichtigt oder ergänzt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht (Art. 97 Abs. 1 BGG bzw. Art. 105 Abs. 2 BGG). Eine entsprechende Rüge, welche rechtsgenüglich substantiiert vorzubringen ist (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG; vgl. <ref-ruling> E. 1.4.3 S. 254 f.), setzt zudem voraus, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 BGG). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (Art. 99 Abs. 1 BGG).
2. 2.1 Die Ansprüche nach Art. 42 AuG (vgl. E. 1.2 hiervor) erlöschen, wenn sie rechtsmissbräuchlich geltend gemacht werden, namentlich um Vorschriften dieses Gesetzes und seiner Ausführungsbestimmungen über die Zulassung und den Aufenthalt zu umgehen (Art. 51 Abs. 1 lit. a AuG). Hierunter fällt unter anderem die sogenannte Scheinehe oder Ausländerrechtsehe, bei der die Ehegatten von vornherein keine echte eheliche Gemeinschaft beabsichtigen (<ref-ruling> E. 2.2 S. 151 mit Hinweisen).
2.2 Ob eine Scheinehe geschlossen wurde, entzieht sich in der Regel dem direkten Beweis und ist bloss durch Indizien zu erstellen (<ref-ruling> E. 10.2 und 10.3 S. 135 f. mit Hinweisen). Feststellungen über das Bestehen solcher Indizien können äussere Gegebenheiten, aber auch innere, psychische Vorgänge betreffen (Wille der Ehegatten); es handelt sich so oder anders um tatsächliche Feststellungen, welche für das Bundesgericht grundsätzlich verbindlich sind (vgl. E. 1.5 hiervor). Frei zu prüfen ist dagegen die Rechtsfrage, ob die festgestellten Tatsachen (Indizien) darauf schliessen lassen, die Berufung auf die Ehe bezwecke die Umgehung fremdenpolizeilicher Vorschriften oder sei rechtsmissbräuchlich (<ref-ruling> E. 2.3 S. 152 mit Hinweisen).
3. Auf Grund der für das Bundesgericht verbindlichen Sachverhaltsfeststellungen gelangte das Verwaltungsgericht des Kantons Zürich zur Auffassung, es liege eine Scheinehe vor. Dieser Schluss ist nicht zu beanstanden.
3.1 Nicht durchzudringen vermag vorab die Rüge, die Vorinstanz habe den Anspruch auf rechtliches Gehör verletzt, indem sie die (schweizerische) Ehefrau nicht erneut als Zeugin einvernommen bzw. keine öffentliche Gerichtsverhandlung durchgeführt 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 (<ref-ruling> 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 (<ref-ruling> E. 5.3 S. 148 mit Hinweisen). Diese Voraussetzungen waren vorliegend ohne Weiteres erfüllt (vgl. auch E 3.2 hiernach), weshalb von einer Gehörsverletzung nicht die Rede sein kann.
Der von Art. 29 Abs. 2 BV gewährleistete Anspruch auf rechtliches Gehör räumt - entgegen der Auffassung des Beschwerdeführers - in der Regel kein Recht auf eine mündliche Anhörung ein, sondern beschränkt sich auf die Möglichkeit einer schriftlichen Stellungnahme (<ref-ruling> E. 5.3 S. 148 mit Hinweisen). Dass das zürcherische Verfahrensrecht ihm einen weiter gehenden Gehörsanspruch gewährleiste, macht der Beschwerdeführer hier nicht geltend.
Soweit sich der Beschwerdeführer in Zusammenhang mit seinen verfahrensrechtlichen Rügen schliesslich auf Art. 6 EMRK beruft, ist ihm entgegenzuhalten, dass Entscheidungen betreffend Einreise, Aufenthalt und Wegweisung von Ausländern gemäss der ständigen Rechtsprechung des Europäischen Gerichtshofes für Menschenrechte (EGMR) nicht in den Schutzbereich dieser Bestimmung fallen (Urteil des EGMR vom 26. März 2002 Mir gegen Schweiz, publ. in: VPB 2002 Nr. 116 S. 1322, mit weiteren Hinweisen).
3.2 Für die Annahme, der Beschwerdeführer sei mit seiner schweizerischen Ehefrau eine Scheinehe eingegangen, konnte sich die Vorinstanz auf zahlreiche Indizien stützen: So hätte sich der Beschwerdeführer ohne Heirat kein Anwesenheitsrecht in der Schweiz verschaffen können. Besonderes Gewicht hat die Vorinstanz zu Recht den Aussagen des Beschwerdeführers und seiner Ehefrau im Rahmen der polizeilichen Befragungen am 27. bzw. 28. Oktober 2008 beigemessen: Der Beschwerdeführer gab dabei an, nur "ab und zu mal" mit seiner Ehefrau in der gemeinsamen Wohnung übernachtet zu haben. Zudem offenbarten sich eklatante Wissenslücken über das Leben seiner Ehefrau bzw. das eheliche Zusammeleben (Geburtstag der Ehefrau, Körpermerkmale, Umstände des Kennenlernens und der Hochzeit, etc.). Die Ehefrau gab in der Befragung an, die Ehe habe ausschliesslich dazu gedient, dem Beschwerdeführer den weiteren Aufenthalt in der Schweiz zu ermöglichen und es sei ihr als Gegenleistung ein Betrag von Fr. 35'000.-- ausgerichtet worden. Sie führe mit ihrem Lebenspartner Z._ seit acht Jahren eine Beziehung und wohne seit längerem mit ihm zusammen. Unter diesen Umständen ist der Schluss der Vorinstanz, die von der Ehefrau nachträglich am 13. bzw. 22. Oktober 2009 eingereichten Schreiben, vermöchten die vorgenommene Würdigung nicht umzustossen, nicht zu beanstanden: Die Beteuerungen der Ehefrau, sie habe gegenüber der Polizei falsche Angaben gemacht, ihren Ehemann aus Liebe geheiratet und das Ehepaar sei auf der Suche nach einer grösseren Wohnung, durfte die Vorinstanz als "Gefälligkeitshandlungen" unberücksichtigt lassen. Diese Beteuerungen, welche im Übrigen nicht näher belegt werden, vermögen aufgrund des durch zahlreiche Indizien vermittelten Gesamtbildes jedenfalls weder den Nachweis für ein eheliches Zusammenleben noch für das Bestehen einer Ehegemeinschaft zu erbringen.
3.3 Soweit der Beschwerdeführer schliesslich neu (mit separater Eingabe vom 11. Oktober 2010) erstmals vorbringt, er und seine Ehefrau seien auf der Suche nach einer gemeinsamen Wohnung ("Untermieter bei W._") endlich fündig geworden, handelt es sich um ein unzulässiges Novum; die Einzugsanzeige des Bevölkerungsamts der Stadt Zürich vom 30. September 2010 ist als unzulässiges "echtes" Novum aus dem Recht zu weisen (<ref-ruling> E. 2.1 S. 344 mit Hinweisen).
Das blosse Zusammenwohnen würde im Übrigen nicht für eine nachträgliche Wandlung einer Scheinehe zu einer echten Lebensgemeinschaft genügen (vgl. zum "amor superveniens" <ref-ruling> E. 2d S. 4 f.; Urteil 2A.66/2007 vom 12. Juni 2007 E. 3.7); konkrete Anhaltspunkte für eine derartige Entwicklung der ehelichen Beziehung sind vorliegend weder dargetan noch ersichtlich.
3.4 Schliesslich macht der Beschwerdeführer zu Recht nicht (mehr) geltend, dass er nach Art. 50 Abs. 1 lit. b AuG weiter Anspruch auf Verlängerung der Aufenthaltsbewilligung habe: Wichtige persönliche Gründe, die einen weiteren Aufenthalt in der Schweiz erforderlich machten, sind - wie die Vorinstanz zu Recht festgestellt hat - nicht ersichtlich.
4. 4.1 Die Verweigerung der Verlängerung der Aufenthaltsbewilligung verstösst somit weder gegen Bundesrecht noch gegen Völkerrecht. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist abzuweisen, soweit darauf eingetreten werden kann. Auf die subsidiäre Verfassungsbeschwerde ist nicht einzutreten (vgl. E. 1.3 hiervor). Bei diesem Ergebnis besteht auch kein Anlass, dem Eventualantrag (Rückweisung der Sache an die Vorinstanz zwecks Vervollständigung des Sachverhalts) stattzugeben.
4.2 Dem Verfahrensausgang entsprechend sind die Gerichtskosten dem unterliegenden Beschwerdeführer aufzuerlegen (Art. 66 Abs. 1 BGG). Es ist keine Parteientschädigung geschuldet (Art. 68 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen, soweit darauf einzutreten ist.
2. Auf die subsidiäre Verfassungsbeschwerde wird nicht eingetreten.
3. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird dem Beschwerdeführer, der Sicherheitsdirektion und dem Regierungsrat des Kantons Zürich, dem Verwaltungsgericht des Kantons Zürich, 2. Kammer, sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 6. Dezember 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Zünd Winiger