Sachverhalt: Sachverhalt: A. Der aus Serbien/Montenegro stammende X._ (geboren am ... 1978) reiste im Jahr 2000 mit einem falschen Pass und ohne Bewilligung in die Schweiz ein. Er hielt sich bei seiner 1981 geborenen Freundin Y._ in A._ auf, einer ursprünglich ebenfalls serbischen Staatsangehörigen, die im Jahr 1999 die schweizerische Staatsangehörigkeit erworben hatte. Nachdem X._ die Schweiz vorübergehend verlassen hatte, reiste er im Januar 2001 erneut mit falschem Pass und ohne Bewilligung zu seiner Bekannten. Am 14. März 2001 wurde er verhaftet. Am 12. Juni 2001 heiratete er in der Untersuchungshaft Y._. Mit rechtskräftigem Urteil vom 14. November 2001 sprach das Bezirksgericht B._ X._ schuldig des gewerbs- und bandenmässigen Diebstahls, der mehrfachen Sachbeschädigung, des mehrfachen Hausfriedensbruchs, der Entwendung zum Gebrauch, der falschen Anschuldigung sowie der Widerhandlung gegen das Waffengesetz und das Bundesgesetz vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; SR 142.20) und verurteilte ihn zu zwei Jahren Gefängnis. X._ trat am 30. Juli 2001 den Strafvollzug an und wurde am 13. Juli 2002 vorzeitig und bedingt entlassen. Mit rechtskräftigem Urteil vom 14. November 2001 sprach das Bezirksgericht B._ X._ schuldig des gewerbs- und bandenmässigen Diebstahls, der mehrfachen Sachbeschädigung, des mehrfachen Hausfriedensbruchs, der Entwendung zum Gebrauch, der falschen Anschuldigung sowie der Widerhandlung gegen das Waffengesetz und das Bundesgesetz vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; SR 142.20) und verurteilte ihn zu zwei Jahren Gefängnis. X._ trat am 30. Juli 2001 den Strafvollzug an und wurde am 13. Juli 2002 vorzeitig und bedingt entlassen. B. Am 19. Juli 2002 wies die Direktion für Soziales und Sicherheit (Migrationsamt) des Kantons Zürich ein Gesuch von X._ um Erteilung einer Aufenthaltsbewilligung nach der Entlassung aus dem Strafvollzug ab. Erfolglos beschwerte er sich dagegen beim Regierungsrat und in der Folge beim Verwaltungsgericht des Kantons Zürich. Mit Eingabe vom 9. Januar 2004 hat X._ beim Bundesgericht Verwaltungsgerichtsbeschwerde erhoben. Er beantragt, den Entscheid des Verwaltungsgerichts vom 22. Oktober 2003 aufzuheben und ihm eine Aufenthaltsbewilligung zu erteilen; eventualiter sei die Sache zur weiteren Sachverhaltsabklärung an die Vorinstanz zurückzuweisen. Zudem stellt er das Begehren, ihm sei während dem bundesgerichtlichen Beschwerdeverfahren der Aufenthalt und Arbeitserwerb im Kanton Zürich zu gestatten. Die Staatskanzlei des Kantons Zürich, im Auftrag des Regierungsrates, und das Bundesamt für Zuwanderung, Integration und Auswanderung schliessen auf Abweisung der Beschwerde. Das Verwaltungsgericht beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Die Staatskanzlei des Kantons Zürich, im Auftrag des Regierungsrates, und das Bundesamt für Zuwanderung, Integration und Auswanderung schliessen auf Abweisung der Beschwerde. Das Verwaltungsgericht beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei. C. Mit Präsidialverfügung vom 9. Februar 2004 wurde der Beschwerde aufschiebende Wirkung zuerkannt.