Sachverhalt:
A. Mit Urteil vom 19. Dezember 2008 sprach das Obergericht des Kantons Zürich X._ des gewerbsmässigen Betrugs (Art. 146 Abs. 1 und 2 StGB) und der mehrfachen Urkundenfälschung (<ref-law>) schuldig und verurteilte ihn zu einer Freiheitsstrafe von 33 Monaten, unter Anrechnung der erstandenen Untersuchungshaft von 46 Tagen.
B. X._ führt Beschwerde in Strafsachen mit den Anträgen, das Urteil des Obergerichts des Kantons Zürich vom 19. Dezember 2008 sei aufzuheben, und die Sache sei im Sinne der Erwägungen an die Vorinstanz zurückzuweisen.
Das Obergericht des Kantons Zürich hat auf eine Stellungnahme zur Beschwerde verzichtet. Die Oberstaatsanwaltschaft des Kantons Zürich beantragt die Abweisung der Beschwerde.

Erwägungen:
1. Die Verurteilung des Beschwerdeführers basiert auf folgendem Sachverhalt:
Der Beschwerdeführer hat zwischen dem 19. Juni 2004 und 27. September 2004 in insgesamt 24 Fällen zusammen mit M._ und N._ Zahlungsbetrüge durchgeführt respektive durchzuführen versucht. M._ und N._ öffneten mittels eines nachgemachten Schlüssels zahlreiche Postbriefkästen und behändigten an Banken und an die Postfinance adressierte Briefe mit Zahlungsaufträgen. Diese übergaben sie dem Beschwerdeführer, welcher jeweils einen Einzahlungsschein durch einen anderen, auf ein bestimmtes Zielkonto lautenden Einzahlungsschein gleichen Betrags ersetzte. In der Folge wurden die Zahlungsaufträge wieder in den Postverkehr gebracht. Die Fälschungen im Gesamtbetrag von Fr. 744'843.05 wurden bei der Auftragsverarbeitung durch die Banken respektive die Postfinance teilweise erkannt und die Ausführung der Zahlungsaufträge in diesen Fällen dementsprechend verweigert. Insgesamt wurden Fr. 366'008.-- auf die Zielkonti der Täterschaft überwiesen, welche die einbezahlten Gelder durch Schalter- und Automatenbezüge abhob (vgl. angefochtenes Urteil S. 15 f. und S. 24).
2. 2.1 Der Beschwerdeführer rügt eine willkürliche Anwendung des kantonalen Prozessrechts und beruft sich dabei auf einen in einer anderen Sache ergangenen Zirkulationsbeschluss des Kassationsgerichts des Kantons Zürich vom 25. September 2008. Aus diesem Beschluss ergebe sich entgegen den Ausführungen im angefochtenen Urteil, dass der Mangel auch bloss teilweiser ungenügender Verteidigung im Berufungsverfahren nicht geheilt werden könne, sondern gestützt auf <ref-law>/ZH zwingend eine Aufhebung des erstinstanzlichen Entscheids und eine Rückweisung zur Neubeurteilung an die erste Instanz hätte erfolgen müssen (Beschwerde S. 3-5).
2.2 Die Vorinstanz erwägt, der Verteidiger des Beschwerdeführers habe vor der Vorinstanz ein ausführliches Plädoyer gehalten und dabei zur Frage der Strafzumessung insoweit Stellung genommen, als er eingewendet habe, die Schuldfähigkeit seines Mandanten sei allenfalls vermindert. Damit sei ihm offensichtlich auch bewusst gewesen, dass ein Schuldspruch erfolgen könnte. Die erste Instanz habe ihn unter diesen Umständen nicht explizit darauf hinweisen müssen, zur restlichen Strafzumessung Stellung zu nehmen. Im Übrigen sei die Verteidigung im erstinstanzlichen Verfahren auch nicht vollumfänglich, sondern höchstens teilweise ungenügend gewesen, weshalb die Heilbarkeit des Mangels im Berufungsverfahren zu bejahen sei (angefochtenes Urteil S. 15).
2.3 Die Vorinstanz ist der Auffassung, die erste Instanz habe den Verteidiger des Beschwerdeführers nicht explizit darauf hinweisen müssen, in seinem Plädoyer über die Frage der Schuldfähigkeit hinaus zu weiteren Aspekten der Strafzumessung Stellung zu beziehen. Sie geht mithin von einer gehörigen Verteidigung aus. Ihre Ausführungen zur Heilbarkeit eines allfälligen Mangels erfolgen im Sinne einer Eventualerwägung.
Der Beschwerdeführer setzt sich in seiner Beschwerde einzig mit der Frage der Heilbarkeit auseinander, ohne zur Hauptbegründung Stellung zu beziehen. Er legt mithin nicht dar, und es ist auch nicht ersichtlich, inwiefern die Annahme der Vorinstanz, es habe eine gehörige Verteidigung bestanden, Bundesrecht verletzen sollte. Die Beschwerde ist in diesem Punkt abzuweisen, soweit darauf eingetreten werden kann.
3. 3.1 Der Beschwerdeführer macht eine Verletzung seines Anspruchs auf rechtliches Gehör geltend. Zur Begründung führt er aus, indem die Vorinstanz bei ihrer Beweiswürdigung nicht auf seine entscheiderheblichen Einwände bezüglich des Einsatzes einer Videokamera und der Verwertbarkeit der Ergebnisse der durchgeführten Telefonkontrolle eingegangen sei, habe sie <ref-law> verletzt (Beschwerde S. 5 -9).
3.2 Die Vorinstanz erwägt im Rahmen der Beweiswürdigung, M._ und N._ hätten in zahlreichen Einvernahmen eingestanden, dass sie jeweils die entwendeten Zahlungsaufträge zum Beschwerdeführer nach Hause gebracht hätten. Es sei schlechterdings nicht einzusehen, weshalb die beiden den Beschwerdeführer zu Unrecht beschuldigt haben sollten, zumal sie sich mit ihren Aussagen auch selbst belasteten. Im Übrigen habe M._ den Beschwerdeführer entgegen dessen Vorbringen von sich aus und nicht erst unter Druck der vorgehaltenen Observationsberichte belastet. Des Weiteren seien in der Wohnung des Beschwerdeführers Materialien sichergestellt worden, welche sich durchaus zur Fälschung von Zahlungsaufträgen eigneten, nämlich verschiedene Einweghandschuhe und eine Vielzahl von Bögen mit Abreibbuchstaben. Die Stellungnahme des Beschwerdeführers zu diesen Beweismitteln sei alles andere als überzeugend ausgefallen. Zusammenfassend hält die Vorinstanz fest, aufgrund des klaren Beweisergebnisses, das heisst insbesondere angesichts der lebensnahen und detaillierten Aussagen von M._ und N._ sei der eingeklagte Sachverhalt als erstellt anzusehen (angefochtenes Urteil S. 26-28).
3.3 Gemäss <ref-law> haben die Parteien Anspruch auf rechtliches Gehör. Die betroffene Person hat das Recht, sich vor Erlass eines in ihre Rechtsstellung eingreifenden Entscheids zur Sache zu äussern. Dazu gehört insbesondere das Recht, Einsicht in die Akten zu nehmen, mit erheblichen Beweisanträgen gehört zu werden und an der Erhebung wesentlicher Beweise entweder mitzuwirken oder sich zumindest zum Beweisergebnis zu äussern, wenn es geeignet ist, den Entscheid zu beeinflussen. Wesentlicher Bestandteil des Anspruchs auf rechtliches Gehör ist die Begründungspflicht. Genannt werden müssen wenigstens kurz die Überlegungen, von denen sich die Behörde hat leiten lassen und auf welche sich ihr Entscheid stützt. Dies bedeutet indessen nicht, dass sie sich ausdrücklich mit jeder tatbeständlichen Behauptung und jedem rechtlichen Einwand auseinandersetzen muss. Vielmehr kann sie sich auf die für den Entscheid wesentlichen Gesichtspunkte beschränken (<ref-ruling> E. 3.1; <ref-ruling> E. 3.2).
3.4 Die Vorinstanz legt eingehend dar, weshalb sie den Sachverhalt gestützt auf die belastenden Aussagen von M._ und N._ sowie die beim Beschwerdeführer aufgefundenen Gegenstände als nachgewiesen erachtet. Auf Ergebnisse aus allfälligen Überwachungen des Beschwerdeführers mittels technischen Überwachungsgeräten oder seines Fernmeldeverkehrs wird in der Urteilsbegründung nicht Bezug genommen. Es stellt daher auch keine Verletzung des Anspruchs des Beschwerdeführers auf rechtliches Gehör dar, dass die Vorinstanz sich mangels Entscheiderheblichkeit nicht mit seinen diesbezüglichen Vorbringen auseinandersetzt.
4. 4.1 Der Beschwerdeführer wendet sich weiter gegen die Strafzumessung und rügt eine Verletzung von Art. 47 f. StGB. Er betont vorab, das vorinstanzliche Urteil sei erst vier Jahre nach den ihm vorgeworfenen Taten ergangen. Analog zu <ref-law> habe sich der Ablauf einer erheblichen Zeitspanne seit der Tat respektive die relativ lange Verfahrensdauer strafmindernd auszuwirken, zumal er in dieser Zeit nicht mehr deliktisch in Erscheinung getreten sei. Des Weiteren sei die deutlich straferhöhende Berücksichtigung des Rückfalls durch die Vorinstanz mit dem Schuldprinzip kaum zu vereinbaren und verstosse gegen <ref-law>. Zudem sei ihm zu Unrecht keine erhöhte Strafempfindlichkeit zugebilligt worden, obwohl er verheiratet und Vater von zwei Kindern sei. Schliesslich habe die Vorinstanz das Doppelverwertungsverbot verletzt, indem sie die Deliktsmehrheit und die mehrfache Tatbegehung straferhöhend bewertet habe, seien diese Umstände doch bereits bei der Qualifikation der Delikte als gewerbsmässiger Betrug und als mehrfache Urkundenfälschung einbezogen worden (Beschwerde S. 9-11).
4.2 Die Vorinstanz erwägt, das Tatverschulden des Beschwerdeführers wiege insbesondere angesichts des hohen Deliktsbetrags schwer. Das Vorgehen der "Zaire Connection" zeuge von grosser Professionalität und Raffinesse, wobei sich der Beschwerdeführer als eigentlicher Spezialist der Bande erwiesen und einen sehr wesentlichen Tatbeitrag geleistet habe. Sein Verhalten lasse auf einen ausgeprägten deliktischen Willen bzw. eine grosse kriminelle Energie und auf eine erhebliche Uneinsichtigkeit schliessen. Erschwerend ins Gewicht falle, dass er einzig aus finanziellen Motiven und nicht aus einer Notlage heraus gehandelt habe. Straferhöhend innerhalb des ordentlichen Strafrahmens zu berücksichtigen seien sodann die Deliktsmehrheit und die mehrfache Tatbegehung. Strafmilderungsgründe seien keine ersichtlich; insbesondere bestünde kein ernsthafter Anlass, an seiner Schuldfähigkeit zu zweifeln. In Würdigung der massgeblichen Strafzumessungsgründe erweise sich eine Freiheitsstrafe von 33 Monaten als dem Verschulden und den persönlichen Verhältnissen des Beschwerdeführers angemessen (angefochtenes Urteil S. 39-41).
4.3 Gemäss <ref-law> misst das Gericht die Strafe nach dem Verschulden des Täters zu. Es berücksichtigt das Vorleben, die persönlichen Verhältnisse sowie die Wirkung der Strafe auf das Leben des Täters. Die Bewertung des Verschuldens wird in <ref-law> dahingehend präzisiert, dass dieses nach der Schwere der Verletzung oder Gefährdung des betroffenen Rechtsguts, nach der Verwerflichkeit des Handelns, den Beweggründen und Zielen des Täters sowie danach bestimmt wird, wie weit der Täter nach den inneren und äusseren Umständen in der Lage war, die Gefährdung oder Verletzung zu vermeiden. Nach <ref-law> hat das Gericht die für die Zumessung der Strafe erheblichen Umstände und deren Gewichtung festzuhalten.
Es liegt im Ermessen des Sachgerichts, in welchem Umfang es die verschiedenen Strafzumessungsfaktoren berücksichtigt. Das Bundesgericht greift auf Beschwerde hin nur in die Strafzumessung ein, wenn die Vorinstanz den gesetzlichen Strafrahmen über- oder unterschreitet, wenn sie von rechtlich nicht massgebenden Kriterien ausgeht oder wesentliche Gesichtspunkte ausser Acht lässt bzw. in Überschreitung oder Missbrauch ihres Ermessens falsch gewichtet (vgl. <ref-ruling> E. 2.1).
4.4 Die Vorinstanz würdigt im angefochtenen Urteil die für die Zumessung der Strafe erheblichen Umstände eingehend. Sie setzt sich ausführlich mit den objektiven und subjektiven Verschuldenskomponenten auseinander.
4.4.1 Soweit sich der Beschwerdeführer auf <ref-law> beruft, ist seine Argumentation nicht stichhaltig. Gemäss dieser Bestimmung mildert das Gericht die Strafe, wenn das Strafbedürfnis in Anbetracht der seit der Tat verstrichenen Zeit deutlich vermindert ist und der Täter sich in dieser Zeit wohlverhalten hat. Dieser Strafmilderungsgrund stellt einen Konnex zwischen Zeitablauf und fehlendem Strafbedürfnis her. Nach der bundesgerichtlichen Rechtsprechung zu Art. 64 zweitletzter Absatz aStGB, welcher materiell mit <ref-law> übereinstimmt, hat eine Strafmilderung zu erfolgen, wenn zwei Drittel der Verjährungsfrist verstrichen sind (<ref-ruling> E. 6.2).
Der Beschwerdeführer hat die zu beurteilenden Delikte im Sommer 2004 verübt. Damit liegen diese nicht derart weit zurück, dass die Vorinstanz gehalten gewesen wäre, dem Zeitablauf seit der Tat mit einer Strafmilderung oder - wie vom Beschwerdeführer gefordert - in analoger Anwendung von <ref-law> zumindest mit einer Strafminderung Rechnung zu tragen.
4.4.2 Der Beschwerdeführer wurde mit Urteil des Gerichtskreises VIII Bern-Laupen vom 11. Juli 2000 wegen versuchten Betrugs und Urkundenfälschung zu einer bedingten Gefängnisstrafe von zwölf Monaten bei einer Probezeit von fünf Jahren und zu einer bedingten Landesverweisung von sieben Jahren verurteilt. Die Vorinstanz verletzt kein Bundesrecht, indem sie diese einschlägige Vorstrafe deutlich straferhöhend berücksichtigt. Die Erwägung im angefochtenen Urteil, der Beschwerdeführer habe sich offenbar von dieser Verurteilung völlig unbeeindruckt gezeigt, was auf eine erhebliche Uneinsichtigkeit und grosse kriminelle Energie schliessen lasse (angefochtenes Urteil S. 39 f.), ist nicht zu beanstanden.
4.4.3 Ferner ist der Beschwerde kein Erfolg beschieden, soweit eine besondere Strafempfindlichkeit geltend gemacht wird. Zwar können bei den Wirkungen der Strafe auf das Leben des Täters unter dem Gesichtspunkt der Strafempfindlichkeit auch die berufliche und die familiäre Situation Berücksichtigung finden. Die Verbüssung einer Freiheitsstrafe ist jedoch für jeden arbeitstätigen und in ein familiäres Umfeld eingebetteten Beschuldigten mit einer gewissen Härte verbunden. Als unmittelbare gesetzmässige Folge jeder Sanktion darf diese Konsequenz daher nur bei Vorliegen aussergewöhnlicher Umstände (erheblich) strafmindernd wirken (Hans Wiprächtiger, Basler Kommentar, Strafgesetzbuch I, 2. Aufl., 2007, Art. 47 N. 118).
Die Vorinstanz würdigt die berufliche Situation und die familiären Verhältnisse des Beschwerdeführers. Ihr Schluss, es lägen keine aussergewöhnlichen Umstände vor, welche zu einer über das durchschnittliche Mass hinausreichenden Strafempfindlichkeit führten, verstösst nicht gegen <ref-law>.
4.4.4 Das Doppelverwertungsverbot, welches der Beschwerdeführer als verletzt rügt, bedeutet, dass Qualifikations- und Privilegierungsgründe, die zu einem veränderten Strafrahmen führen, nicht ein zweites Mal berücksichtigt werden dürfen. Das Gericht kann jedoch einbeziehen, in welchem Ausmass ein qualifizierender oder ein privilegierender Tatumstand gegeben ist (Stefan Trechsel/Heidi Affolter-Eijsten, Schweizerisches Strafgesetzbuch - Praxiskommentar, 2008, Art.47 N. 27).
Die Vorinstanz führt in ihrer Urteilsbegründung insoweit einzig aus, die Deliktsmehrheit und die mehrfache Tatbegehung fielen straferhöhend ins Gewicht. Es ist daher fraglich, ob sie einzig dem Ausmass der Verfehlungen des Beschwerdeführers innerhalb der qualifizierten Tatbestände des gewerbsmässigen Betrugs (Art. 146 Abs. 1 und 2 StGB) bzw. der mehrfachen Urkundenfälschung (<ref-law>) Rechnung trägt oder aber in Verletzung des Doppelverwertungsverbots die Tatmehrheit ein zweites Mal veranschlagt.
Diese Frage kann jedoch letztlich offen gelassen werden, denn das Bundesgericht kann ein angefochtenes Urteil auch bestätigen, wenn dieses in Bezug auf die Erwägungen zum Strafmass einzelne Unklarheiten und Unvollkommenheiten enthält, solange sich die Strafe unter Beachtung aller relevanten Faktoren - wie im zu beurteilenden Fall - offensichtlich im Rahmen des dem Sachgericht zustehenden Ermessens hält (Urteil des Bundesgerichts 6B_341/2007 vom 17. März 2008 E. 8.4, nicht publ. in: <ref-ruling>). Die Erwägungen der Vorinstanz sind insgesamt plausibel und ihre gezogenen Schlüsse leuchten ein. Sie gewichtet zusammenfassend die relevanten Strafzumessungsfaktoren nachvollziehbar und verletzt angesichts des insgesamt schweren Verschuldens des Beschwerdeführers mit der verhängten Freiheitsstrafe von 33 Monaten das ihr zustehende Ermessen auch im Lichte der bundesgerichtlichen Rechtsprechung nicht.
5. 5.1 Der Beschwerdeführer rügt im Zusammenhang mit der Verweigerung des teilbedingten Strafvollzugs eine Verletzung der Art. 43 und 369 StGB. Er betont, seine beiden aus dem Strafregister entfernten Vorstrafen aus dem Jahr 1997 hätten von der Vorinstanz bei der Prognosebeurteilung im Rahmen von <ref-law> nicht zu seinen Ungunsten berücksichtigt werden dürfen, statuiere doch <ref-law> explizit ein Verwertungsverbot. Überdies habe die Vorinstanz insoweit fälschlicherweise geprüft, ob eine günstige Prognose bestehe. Entscheidend sei vielmehr, dass keine Anhaltspunkte für eine ungünstige Prognose vorlägen. Zu würdigen sei, dass er seit acht Jahren verheiratet sei, zwei Kinder habe und seit Jahren als Gärtner arbeitstätig sei. Ohne Einbezug der beiden entfernten Vorstrafen aus dem Jahr 1997 könne folglich zusammenfassend nicht von einer Schlechtprognose ausgegangen werden, weshalb die Verweigerung des teilbedingten Strafvollzugs gegen <ref-law> verstosse (Beschwerde S. 12-14).
5.2 Die Vorinstanz hält unter Bezugnahme auf das erstinstanzliche Urteil fest, angesichts der drei teilweise einschlägigen Vorstrafen und dem Umstand, dass der Beschwerdeführer während einer laufenden Probezeit delinquiert habe, könne ihm keine günstige Prognose gestellt werden, weshalb die gesamte Strafe zu vollziehen sei (angefochtenes Urteil S. 41).
5.2 Die Vorinstanz hält unter Bezugnahme auf das erstinstanzliche Urteil fest, angesichts der drei teilweise einschlägigen Vorstrafen und dem Umstand, dass der Beschwerdeführer während einer laufenden Probezeit delinquiert habe, könne ihm keine günstige Prognose gestellt werden, weshalb die gesamte Strafe zu vollziehen sei (angefochtenes Urteil S. 41).
5.3 5.3.1 Unter dem Titel "Entfernung des Eintrags" werden in <ref-law> Fristen festgelegt, nach deren Ablauf Einträge aus dem Strafregister zu entfernen sind. Urteile, die eine bedingte Freiheitsstrafe, eine Geldstrafe, gemeinnützige Arbeit oder eine Busse als Hauptstrafe enthalten, werden von Amtes wegen nach zehn Jahren entfernt (<ref-law>). Diese Entfernungsfrist beginnt ab Rechtskraft des Urteils zu laufen und kann nicht verlängert werden (Patrick Gruber, Basler Kommentar StGB II, 2. Aufl., Basel 2007, Art. 369 N. 32). Nach der Entfernung darf die Eintragung nicht mehr rekonstruierbar sein. Das entfernte Urteil darf dem Betroffenen nicht mehr entgegengehalten werden (<ref-law>).
Aus dem gesetzgeberischen Willen der vollständigen Rehabilitation ist zu folgern, dass entfernte Urteile weder bei der Strafzumessung noch bei der Prognosebeurteilung zulasten der betroffenen Person berücksichtigt werden dürfen. Nach Ablauf der Entfernungsfrist von <ref-law> sind die Rehabilitierungs- und Resozialisierungsinteressen der betroffenen Person mithin von Gesetzes wegen stärker zu gewichten als die öffentlichen Informations- und Strafbedürfnisse (<ref-ruling> E. 2.5 mit Hinweisen).
5.3.2 Der Beschwerdeführer ist dreifach vorbestraft. Neben der erwähnten Verurteilung aus dem Jahr 2000 (vgl. E. 4.4.2 hiervor) wurde er mit Strafmandat des Polizeigerichts Basel-Stadt vom 20. März 1997 wegen rechtswidriger Einreise, Verwendung oder Verschaffung gefälschter fremdenpolizeilicher Ausweispapiere und rechtswidrigen Aufenthalts verurteilt und mit einer bedingten Gefängnisstrafe von 14 Tagen bei einer Probezeit von zwei Jahren bestraft. Ferner wurde er mit Urteil des Gerichtskreises VIII Bern-Laupen vom 17. September 1997 der Fälschung von Ausweisen (teilweise in Gehilfenschaft) und der Gehilfenschaft zum Betrug für schuldig befunden und zu einer bedingten Gefängnisstrafe von sechs Monaten, unter Ansetzung einer Probezeit von drei Jahren, sowie zu einer Landesverweisung von fünf Jahren verurteilt.
5.3.3 Die beiden Urteile aus dem Jahr 1997, mit welchen der Beschwerdeführer zu bedingten Gefängnisstrafen verurteilt worden ist, waren zum Zeitpunkt des erstinstanzlichen Urteils vom 20. Dezember 1997 aus dem Strafregister entfernt bzw. haben jedenfalls als entfernt zu gelten, weshalb sie dem Beschwerdeführer im Rahmen seiner Prognosebeurteilung nicht mehr hätten entgegengehalten werden dürfen. Die Vorinstanz missachtet damit Art. 369 Abs. 3 i.V.m. Abs. 7 StGB. Zu klären bleibt, ob sich diese Bundesrechtsverletzung nachteilig ausgewirkt hat, was der Fall ist, wenn bei Beachtung des Verwertungsverbots der beiden Vorstrafen in Anwendung von <ref-law> die Gewährung des teilbedingten Strafvollzugs in Betracht gekommen wäre.
5.3.3 Die beiden Urteile aus dem Jahr 1997, mit welchen der Beschwerdeführer zu bedingten Gefängnisstrafen verurteilt worden ist, waren zum Zeitpunkt des erstinstanzlichen Urteils vom 20. Dezember 1997 aus dem Strafregister entfernt bzw. haben jedenfalls als entfernt zu gelten, weshalb sie dem Beschwerdeführer im Rahmen seiner Prognosebeurteilung nicht mehr hätten entgegengehalten werden dürfen. Die Vorinstanz missachtet damit Art. 369 Abs. 3 i.V.m. Abs. 7 StGB. Zu klären bleibt, ob sich diese Bundesrechtsverletzung nachteilig ausgewirkt hat, was der Fall ist, wenn bei Beachtung des Verwertungsverbots der beiden Vorstrafen in Anwendung von <ref-law> die Gewährung des teilbedingten Strafvollzugs in Betracht gekommen wäre.
5.4 5.4.1 Gemäss <ref-law> schiebt das Gericht den Vollzug einer Freiheitsstrafe von mindestens sechs Monaten und höchstens zwei Jahren in der Regel auf, wenn eine unbedingte Strafe nicht notwendig erscheint, um den Täter von der Begehung weiterer Verbrechen oder Vergehen abzuhalten (<ref-law>). Eine Besonderheit in der Prognosebildung gilt für den Fall, dass der Täter innerhalb der letzten fünf Jahre vor der Tat zu einer Freiheitsstrafe von mindestens sechs Monaten oder einer Geldstrafe von mindestens 180 Tagessätzen verurteilt worden ist (<ref-law>). Liegt ein Rückfall im Sinne dieser Bestimmung vor, ist der Aufschub nur zulässig, "wenn besonders günstige Umstände vorliegen". Darunter sind solche Umstände zu verstehen, die ausschliessen, dass die Vortat die Prognose verschlechtert. Bei <ref-law> gilt demnach die Vermutung einer günstigen Prognose bzw. des Fehlens einer ungünstigen Prognose nicht. Vielmehr kommt der früheren Verurteilung zunächst die Bedeutung eines Indizes für die Befürchtung zu, dass der Täter weitere Straftaten begehen könnte. Die Gewährung des bedingten Strafvollzuges ist daher nur möglich, wenn eine Gesamtwürdigung aller massgebenden Faktoren den Schluss zulässt, dass trotz der Vortat eine begründete Aussicht auf Bewährung besteht. Dabei ist zu prüfen, ob die indizielle Befürchtung durch die besonders günstigen Umstände zumindest kompensiert wird. Das trifft etwa zu, wenn die neuerliche Straftat mit der früheren Verurteilung in keinerlei Zusammenhang steht, oder bei einer besonders positiven Veränderung in den Lebensumständen des Täters (<ref-ruling> E. 4.2.3).
5.4.2 Nach <ref-law> kann das Gericht den Vollzug einer Freiheitsstrafe von mindestens einem Jahr und höchstens drei Jahren nur teilweise aufschieben, wenn dies notwendig ist, um dem Verschulden des Täters genügend Rechnung zu tragen (<ref-law>). Der unbedingt vollziehbare Teil darf die Hälfte der Strafe nicht übersteigen (<ref-law>); sowohl der aufgeschobene wie auch der zu vollziehende Teil der Freiheitsstrafe muss mindestens sechs Monate betragen (<ref-law>). Grundvoraussetzung für die teilbedingte Strafe im Sinne von <ref-law> ist, dass eine begründete Aussicht auf Bewährung besteht. Zwar fehlt ein entsprechender Verweis auf <ref-law>, doch ergibt sich dies aus Sinn und Zweck von <ref-law>. Die subjektiven Voraussetzungen von <ref-law> gelten mithin auch für die Anwendung von <ref-law> (vgl. <ref-ruling> E. 5.3.1 mit Hinweisen).
5.4.3 Der Beschwerdeführer wurde am 11. Juli 2000 - und damit innerhalb der letzten fünf Jahre vor seiner Tatausführung im Sommer 2004 - wegen versuchten Betrugs und Urkundenfälschung zu einer bedingten Freiheitsstrafe von zwölf Monaten verurteilt, weshalb gestützt auf Art. 42 Abs. 2 i.V.m. <ref-law> besonders günstige Umstände vorliegen müssten, damit ein teilweiser Aufschub der Strafe zulässig wäre (vgl. auch Urteile des Bundesgerichts 6B_540/2007 vom 16. Mai 2008 E. 5.2 und 6B_393/2007 vom 2. November 2007 E. 4).
Dies ist nicht der Fall. Auch ohne die von der Vorinstanz zu Unrecht vorgenommene Berücksichtigung der Vorstrafen des Beschwerdeführers aus dem Jahr 1997 fehlt es vorliegend offensichtlich an solch besonders günstigen Umständen. Gegenteiliges wird im Übrigen selbst vom Beschwerdeführer nicht behauptet, welcher einzig anführt, es könne nicht von einer Schlechtprognose ausgegangen werden. Insbesondere kann nicht gesagt werden, die neuerliche Delinquenz stünde in keinem Zusammenhang mit der einschlägigen Verurteilung wegen versuchten Betrugs und Urkundenfälschung aus dem Jahr 2000. Obwohl der Beschwerdeführer in geordneten familiären und beruflichen Verhältnissen lebt, kann ebenso wenig von einer besonders positiven Veränderung in seinen Lebensumständen gesprochen werden.
5.5 Die Vorinstanz verstösst somit zusammenfassend nicht gegen <ref-law>, indem sie die ausgefällte Freiheitsstrafe von 33 Monaten für vollziehbar erklärt. Im Ergebnis hält damit das angefochtene Urteil der bundesgerichtlichen Überprüfung stand.
6. 6.1 Der Beschwerdeführer bringt schliesslich vor, der Verzicht der Vorinstanz auf die Einholung eines psychiatrischen Gutachtens missachte die Bestimmung von <ref-law>. Sein Hausarzt, Dr. med. D._, habe mit ärztlichem Zeugnis vom 24. November 2004 ausdrücklich bescheinigt, dass er bei ihm unter anderem wegen Depressionen und manischen Phasen in hausärztlicher Behandlung gestanden und überdies vom 29. August bis zum 4. September 2003 stationär in einer psychiatrischen Klinik gewesen sei. Dementsprechend sei von einer mittelgradig verminderten Schuldfähigkeit auszugehen. Zumindest aber wäre die Vorinstanz bei dieser Ausgangslage gehalten gewesen, ihn psychiatrisch begutachten zu lassen (Beschwerde S. 14-17).
6.2 Die Vorinstanz führt aus, Dr. med. D._ sei kein Facharzt für Psychiatrie, sondern Allgemeinpraktiker. Dessen Bestätigung, wonach er den Beschwerdeführer unter anderem wegen psychischen Problemen behandelt habe, könne keine ernsthaften Zweifel an dessen Schuldfähigkeit begründen. Gleiches gelte bezüglich der Tatsache, dass der Beschwerdeführer im August bzw. September 2003 während insgesamt rund einer Woche in einer psychiatrischen Klinik in stationärer Behandlung gewesen sei. Dementsprechend sei von der Anordnung einer sachverständigen Begutachtung i.S.v. <ref-law> abzusehen (angefochtenes Urteil S. 40 f.).
6.3 Gemäss <ref-law>, welcher inhaltlich Art. 13 aStGB entspricht, hat die Untersuchungsbehörde oder das Gericht die sachverständige Begutachtung des Täters durch eine sachverständige Person anzuordnen, wenn ernsthafter Anlass besteht, an der Schuldfähigkeit des Täters zu zweifeln.
<ref-law> gilt nicht nur, wenn das Gericht tatsächlich Zweifel an der Schuldfähigkeit hat, sondern auch, wenn es nach den Umständen des Falls ernsthafte Zweifel haben sollte. Bei der Prüfung dieser Zweifel ist zu berücksichtigen, dass nicht jede geringfügige Herabsetzung der Fähigkeit, sich zu beherrschen, genügt, um eine verminderte Schuldfähigkeit anzunehmen. Die betroffene Person muss vielmehr, zumal der Begriff des normalen Menschen nicht eng zu fassen ist, in hohem Masse in den Bereich des Abnormen fallen. Ihre Geistesverfassung muss nach Art und Grad stark vom Durchschnitt nicht bloss der Rechts-, sondern auch der Verbrechensgenossen abweichen. Die Notwendigkeit, eine sachverständige Person zuzuziehen, ist erst gegeben, wenn Anzeichen vorliegen, die geeignet sind, Zweifel hinsichtlich der vollen Schuldfähigkeit zu erwecken, wie etwa ein Widerspruch zwischen Tat und Täterpersönlichkeit oder ein völlig unübliches Verhalten. Zeigt das Verhalten des Täters vor, während und nach der Tat, dass ein Realitätsbezug erhalten war, dass er sich an wechselnde Erfordernisse der Situation anpassen oder auf eine Gelegenheit zur Tat warten konnte, so hat eine schwere Beeinträchtigung nicht vorgelegen (vgl. zum Ganzen <ref-ruling> E. 3.3; <ref-ruling> E. 5.1, je mit Hinweisen).
6.4 Einem von einer Partei eingereichten medizinischen Bericht kommt rechtlich einzig die Tragweite einer Parteibehauptung zu. Die Vorinstanz begründet willkürfrei, weshalb sie im Ergebnis von der Einschätzung des Hausarztes des Beschwerdeführers, wonach dessen Schuldfähigkeit aufgrund seiner psychischen Probleme wesentlich vermindert oder gar aufgehoben sei, abweicht. Wie die Vorinstanz, ohne Bundesrecht zu verletzen, weiter erwägt, vermag insbesondere auch die Tatsache, dass der Beschwerdeführer im Sommer 2003 - und damit rund ein Jahr vor dem deliktsrelevanten Zeitraum - für einige Tage in stationärer psychiatrischer Behandlung war, keine ernsthaften Zweifel an seiner Schuldfähigkeit zu begründen. Die Taten als solche und deren Ausführung weisen keinerlei Auffälligkeiten auf, welche auf einen Verlust des Realitätsbezugs des Beschwerdeführers hindeuten würden. Vielmehr wird deutlich, dass dieser durchaus in der Lage war, sich an die Situationen anzupassen und auf die richtigen Gelegenheiten zur Tatausführung zu warten. Es fehlt mithin an konkreten Hinweisen auf eine Beeinträchtigung seiner Einsichts- oder Steuerungsfähigkeit zum Tatzeitraum, weshalb die Vorinstanz ohne gegen <ref-law> zu verstossen, von der Anordnung einer psychiatrischen Begutachtung des Beschwerdeführers absehen konnte.
7. Aus diesen Gründen ist die Beschwerde abzuweisen, soweit darauf einzutreten ist. Da das Rechtsmittel von vornherein aussichtslos war, kann dem Gesuch um unentgeltliche Rechtspflege nicht entsprochen werden (<ref-law>).
Bei diesem Verfahrensausgang sind die bundesgerichtlichen Kosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Bei der Festsetzung der Gerichtsgebühr ist seinen finanziellen Verhältnissen Rechnung zu tragen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 1'600.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Strafkammer, schriftlich mitgeteilt.
Lausanne, 29. Oktober 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Favre Stohner