Sachverhalt:
A. Mit Urteil vom 4. September 2007 sprach das Bezirksgericht Meilen X._ des gewerbsmässigen, teilweise bandenmässigen Diebstahls, der mehrfachen Sachbeschädigung und des mehrfachen Hausfriedensbruchs schuldig und verurteilte ihn zu einer Freiheitsstrafe von vier Jahren und drei Monaten (unter Anrechnung von 435 Tagen Untersuchungs- und Sicherheitshaft).
Mit Urteil vom 3. Oktober 2008 befand das Bezirksgericht Meilen X._ des mehrfachen Raubes, des Diebstahls, der Hehlerei, des Betrugs, des Hausfriedensbruchs, der mehrfachen Drohung, der mehrfachen Widerhandlung gegen das Waffengesetz (WG) sowie der Widerhandlung gegen das Bundesgesetz über Aufenthalt und Niederlassung der Ausländer (ANAG) schuldig und bestrafte ihn mit einer Freiheitsstrafe von vier Jahren und sechs Monaten (unter Anrechnung von 218 Tagen Untersuchungs- und Sicherheitshaft).
B. X._ erklärte gegen beide Urteile Berufung ans Obergericht des Kantons Zürich. Die Staatsanwaltschaft erhob Anschlussberufung, welche sie jedoch in beiden Verfahren schliesslich wieder zurückzog.
Nach Vereinigung der beiden Berufungsverfahren bestätigte das Obergericht des Kantons Zürich mit Urteil vom 22. Oktober 2009 die erstinstanzlichen Schuldsprüche, soweit diese nicht bereits in Rechtskraft erwachsen waren, und bestrafte X._ mit fünf Jahren Freiheitsstrafe (unter Anrechnung von 652 Tagen Untersuchungs- und Sicherheitshaft) sowie mit einer Geldstrafe von 90 Tagessätzen à Fr. 30.--.
C. Die Oberstaatsanwaltschaft des Kantons Zürich wie auch X._ führen Beschwerde in Strafsachen ans Bundesgericht.
Die Oberstaatsanwaltschaft beantragt, es sei Dispositivziffer 2 des Urteils des Obergerichts des Kantons Zürich vom 22. Oktober 2009 aufzuheben, und X._ sei mit acht Jahren Freiheitsstrafe (unter Anrechnung von 652 Tagen Untersuchungs- und Sicherheitshaft) sowie mit einer Geldstrafe von 90 Tagessätzen à Fr. 30.-- zu bestrafen. Eventualiter sei die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen.
X._ stellt die Anträge, das angefochtene Urteil sei aufzuheben, und die Sache sei zu neuer Strafzumessung an das Obergericht des Kantons Zürich zurückzuweisen. Des Weiteren ersucht er um Gewährung der unentgeltlichen Rechtspflege.
Vernehmlassungen wurden keine eingeholt.

Erwägungen:
1. Da X._ insbesondere auch verfahrensrechtliche Rügen erhebt, wird dessen Beschwerde vorab behandelt.
I. Beschwerde von X._ (Verfahren 6B_125/2010)
2. 2.1 Der Beschwerdeführer rügt eine Verletzung des Prinzips der Doppelinstanzlichkeit gemäss <ref-law>, wonach die Kantone als letzte kantonale Instanzen obere Gerichte einsetzen, welche als Rechtsmittelinstanzen entscheiden. Vorliegend werde die Doppelinstanzlichkeit zwar in formeller Hinsicht gewahrt, materiell aber missachtet, indem die Vorinstanz erstmals sämtliche Deliktskomplexe gesamthaft beurteilt habe. Dies führe im Ergebnis zu einem Instanzenverlust.
2.2 Vorab ist darauf hinzuweisen, dass die Übergangsfrist gemäss <ref-law> zur Umsetzung von <ref-law> noch nicht abgelaufen ist. Die Bestimmung ist aber ohnehin nicht verletzt. Der Kanton Zürich setzt als letzte kantonale Instanz das Obergericht ein, welches als Rechtsmittelinstanz entscheidet. Die Doppelinstanzlichkeit wird auch in materieller Hinsicht gewahrt. So hat das Bezirksgericht Meilen als erste Instanz eine umfassende Beurteilung der Strafzumessung vorgenommen und sämtliche relevanten Strafzumessungsfaktoren gewürdigt. Diese Würdigung ist von der Vorinstanz überprüft worden. Dass diese nach der Vereinigung der beiden Verfahren - nota bene auf Antrag des Beschwerdeführers - erstmals sämtliche Deliktskomplexe gesamthaft beurteilt und die Sache nicht zur Neubeurteilung an die erste Instanz zurückweist, ist nicht zu beanstanden. Die Vorinstanz verfügt über umfassende Kognition (§ 412 Abs. 1 StPO/ZH) und entscheidet - von vorliegend nicht relevanten Ausnahmekonstellationen abgesehen (§ 424 Abs. 1 StPO/ZH) - reformatorisch und nicht kassatorisch (§ 424 Abs. 2 StPO/ZH).
3. 3.1 Der Beschwerdeführer macht geltend, der Verstoss gegen das Beschleunigungsgebot und die lange Verfahrensdauer seien von der Vorinstanz in Verletzung von Bundesrecht nicht zu seinen Gunsten berücksichtigt worden. Eine unberechtigte Verfahrensverzögerung liege darin begründet, dass die Sache im ersten Verfahren zu Beweisergänzungen an die Untersuchungsbehörde habe zurückgewiesen werden müssen. Fälschlicherweise unbeachtet geblieben seien zudem die Tatsachen, dass sein erstes Delikt mehr als 71⁄2 Jahre zurückliege und er sich seit seiner letzten Tat vor fast drei Jahren wohl verhalten habe.
3. 3.1 Der Beschwerdeführer macht geltend, der Verstoss gegen das Beschleunigungsgebot und die lange Verfahrensdauer seien von der Vorinstanz in Verletzung von Bundesrecht nicht zu seinen Gunsten berücksichtigt worden. Eine unberechtigte Verfahrensverzögerung liege darin begründet, dass die Sache im ersten Verfahren zu Beweisergänzungen an die Untersuchungsbehörde habe zurückgewiesen werden müssen. Fälschlicherweise unbeachtet geblieben seien zudem die Tatsachen, dass sein erstes Delikt mehr als 71⁄2 Jahre zurückliege und er sich seit seiner letzten Tat vor fast drei Jahren wohl verhalten habe.
3.2 3.2.1 Das in <ref-law>, Art. 6 Ziff. 1 EMRK und Art. 14 Ziff. 3 lit. c UNO-Pakt II festgeschriebene Beschleunigungsgebot verpflichtet die Behörden, das Strafverfahren zügig voranzutreiben, um die beschuldigte Person nicht unnötig über die gegen sie erhobenen Vorwürfe im Ungewissen zu lassen. Welche Verfahrensdauer angemessen ist, hängt von den konkreten Umständen ab, die in ihrer Gesamtheit zu würdigen sind. Dabei sind insbesondere die Komplexität des Falls, das Verhalten der beschuldigten Person, die Behandlung des Falls durch die Behörden und dessen Bedeutung für die beschuldigte Person zu berücksichtigen (vgl. <ref-ruling> E. 8; <ref-ruling> E. 3).
3.2.2 In seiner Rechtsprechung zum Beschleunigungsgebot hat das Bundesgericht des Weiteren stets darauf hingewiesen, dass die Verfahrensdauer und die Verjährung auseinanderzuhalten sind (vgl. <ref-ruling> E. 8). Der Berücksichtigung von Verfahrensüberlängen liegt der Gedanke zugrunde, dass Strafverfahren für die Betroffenen eine Belastung darstellen, welche durch Verzögerungen unnötig in die Länge gezogen werden. Die Ratio der Verjährung liegt demgegenüber namentlich in der heilenden Wirkung des Zeitablaufs, welche das Strafbedürfnis vermindert. Dem Verjährungsgedanken wird bei der Strafzumessung unter anderem mit <ref-law> Rechnung getragen. Danach 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 wohl verhalten hat.
Sind die Voraussetzungen beider Bestimmungen erfüllt, das heisst, hat das Verfahren überlange gedauert und liegen die Taten weit zurück, so sind die beiden Aspekte nebeneinander zu beachten (<ref-ruling>, 131; Urteil 6B_440/2008 vom 11. November 2008 E. 6.4).
Sind die Voraussetzungen beider Bestimmungen erfüllt, das heisst, hat das Verfahren überlange gedauert und liegen die Taten weit zurück, so sind die beiden Aspekte nebeneinander zu beachten (<ref-ruling>, 131; Urteil 6B_440/2008 vom 11. November 2008 E. 6.4).
3.3 3.3.1 Das Verfahren gegen den Beschwerdeführer ist umfangreich, stehen bzw. standen doch diverse Delikte zur Diskussion. So ist der Beschwerdeführer wegen mehrfachen Raubes, gewerbsmässigen, teilweise bandenmässigen Diebstahls, Hehlerei, Betrugs, mehrfacher Sachbeschädigung, mehrfachen Hausfriedensbruchs, mehrfacher Drohung, mehrfacher Widerhandlung gegen das WG sowie wegen Widerhandlung gegen das ANAG verurteilt worden. Allein der Verurteilung wegen gewerbsmässigen, teilweise bandenmässigen Diebstahls liegen 43 Diebstähle zugrunde (vgl. angefochtenes Urteil S. 42). Die erstinstanzlichen Urteile umfassen 217 respektive 94 Seiten, der zweitinstanzliche Entscheid erstreckt sich über 74 Seiten.
Der Beschwerdeführer verübte die Taten im Zeitraum von März 2003 bis Juli 2007. Die erstinstanzlichen Urteile datieren vom 4. September 2007 und vom 3. Oktober 2008. In Anbetracht des Umfangs und der Komplexität des Verfahrens hat das Untersuchungsstadium trotz der erforderlichen Beweisergänzungen nicht übermässig lange gedauert. Ebenso wenig verletzt die bisherige gesamte Verfahrensdauer das Beschleunigungsgebot. Diese Beurteilung steht in Einklang mit der bisherigen bundesgerichtlichen Rechtsprechung. So bejahte das Bundesgericht Verletzungen des Beschleunigungsgebots namentlich bei einer Verfahrensdauer von sieben Jahren oder mehr (vgl. Urteile 6S.98/2003 vom 22. April 2004 E. 2.3; 6S.335/2004 vom 23. März 2005 E. 6.5; 6S.400/2006 vom 17. März 2007 E. 5) und befand andererseits, dass eine Verfahrensdauer von rund drei Jahren (<ref-ruling> E. 2) und eine solche von über sechs Jahren (Urteil 6S.467/2004 vom 11. Februar 2005 E. 2.2.2) keinen Verstoss gegen das Beschleunigungsgebot begründeten.
3.3.2 Soweit sich der Beschwerdeführer auf den langen Zeitablauf bzw. sein Wohlverhalten und damit sinngemäss auf <ref-law> beruft, ist seine Argumentation nicht stichhaltig. 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 verübte die Taten, wie erwähnt, im Zeitraum von März 2003 bis Juli 2007. Damit liegen diese nicht derart weit zurück, dass die Vorinstanz gehalten gewesen wäre, dem Zeitablauf bei der Strafzumessung zugunsten des Beschwerdeführers Rechnung zu tragen.
II. Beschwerde der Oberstaatsanwaltschaft (Verfahren 6B_104/ 2010)
4. 4.1 Die Beschwerdeführerin rügt eine Verletzung von Art. 47 und Art. 49 StGB. Die erste Instanz habe den Beschwerdegegner mit ihren zwei Urteilssprüchen im Ergebnis mit einer Freiheitsstrafe von acht Jahren und neun Monaten bestraft. Die nunmehr von der Vorinstanz für dieselben Delikte verhängte Freiheitsstrafe von fünf Jahren sei demgegenüber unhaltbar mild.
Die Beschwerdeführerin betont, die Vorinstanz bewerte das Verschulden des Beschwerdegegners in Bezug auf die Raubdelikte insgesamt als mittelschwer. Die Ausführungen im angefochtenen Urteil sprächen jedoch für ein schweres Tatverschulden. Entgegen der Auffassung der Vorinstanz fielen auch die weiteren dem Beschwerdegegner vorgeworfenen Straftatbestände verschuldensmässig nicht weniger stark ins Gewicht. Zudem habe dieser erst aufgrund der erdrückenden Beweislage ein Teilgeständnis abgelegt und sich im Übrigen ausgesprochen uneinsichtig gezeigt, was auch dadurch untermauert werde, dass er gemäss dem Rapport der Stadtpolizei Zürich vom 27. November 2008 am 3. November 2008 - das heisst einen Monat nach seiner zweiten Verurteilung durch das Bezirksgericht Meilen - erneut einen Ladendiebstahl begangen hat. Zusammenfassend erscheine eine Freiheitsstrafe von acht Jahren dem schweren Verschulden und dem völlig uneinsichtigen Verhalten des Beschwerdegegners angemessen. Die Ausfällung einer zusätzlichen Geldstrafe wegen Widerhandlung gegen das ANAG werde nicht angefochten.
4.2 Die Vorinstanz führt aus, als schwerste Straftatbestände erwiesen sich die beiden Raubtaten sowie der bandenmässige Diebstahl, welche beide eine Strafandrohung von Geldstrafe von mindestens 180 Tagessätzen bis zu Freiheitsstrafe von zehn Jahren vorsähen. Aufgrund der Tatmehrheit erweitere sich der ordentliche Strafrahmen auf bis zu 15 Jahre Freiheitsstrafe (angefochtenes Urteil S. 41).
Bezüglich der Tatkomponenten erwägt die Vorinstanz, der Beschwerdegegner sei bei seinen Raubdelikten überlegt, zielgerichtet und skrupellos vorgegangen. In einem Fall habe er dem Opfer gar seine mitgeführte Waffe an den Hals gehalten. Zudem habe er innerhalb von rund 21 Monaten 43 Diebstähle verübt und einen Betrag von Fr. 450'000.-- erbeutet. Damit habe er ein beträchtliches Mass an krimineller Energie offenbart. Die weiteren Tatbestände fielen demgegenüber verschuldensmässig weniger ins Gewicht. Insgesamt sei das Tatverschulden als mittelschwer zu bewerten (angefochtenes Urteil S. 42 f.). Von der subjektiven Tatschwere her erfahre der Beschwerdegegner keine Entlastung. Er habe aus rein egoistischen Motiven gehandelt, und die Intensität seines deliktischen Willens sei sehr ausgeprägt (angefochtenes Urteil S. 44 f.). Für die Raubdelikte erscheine eine hypothetische Einsatzstrafe von 21⁄2 bis drei Jahren Freiheitsstrafe angemessen, welche in Anwendung des Asperationsprinzips gemäss <ref-law> aufgrund der Vielzahl der Delikte zu erhöhen sei (angefochtenes Urteil S. 45).
Betreffend die Täterkomponenten hält die Vorinstanz fest, die beiden Vorstrafen des Beschwerdegegners aus den Jahren 2002 (Verurteilung zu einer Busse von Fr. 800.-- wegen grober Verletzung der Verkehrsregeln und fahrlässiger Körperverletzung) und 2003 (Verurteilung zu einer Busse von Fr. 500.-- wegen Drohung) fielen leicht straferhöhend ins Gewicht. Erheblich straferhöhend wirke sich aus, dass der Beschwerdegegner trotz seiner Verhaftung und laufendem Untersuchungs- bzw. Gerichtsverfahren weiter delinquiert habe (angefochtenes Urteil S. 46 f.). Zudem habe er anfangs sämtliche Delikte bestritten und sich erst angesichts des ihn belastenden Beweisergebnisses teilweise geständig gezeigt. Das Teilgeständnis sei daher nur leicht strafmindernd einzubeziehen. Nachdem der Beschwerdegegner seit Ende 2007 nicht mehr deliktisch in Erscheinung getreten sei und insbesondere seine deliktsorientierte Therapie erfolgreich abgeschlossen habe, sei ein Wandel in seinem Leben unverkennbar, was in geringem Mass strafmindernd Berücksichtigung verdiene (angefochtenes Urteil S. 48 f.).
Zusammenfassend folgert die Vorinstanz, die von der ersten Instanz ausgefällte Freiheitsstrafe von insgesamt acht Jahren und neun Monaten erscheine deutlich zu hoch. Als dem Verschulden des Beschwerdegegners angemessen sei eine Freiheitsstrafe von fünf Jahren einzustufen (angefochtenes Urteil S. 50 f.).
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).
<ref-law> bestimmt, dass das Gericht einen Täter, welcher durch eine oder mehrere Handlungen die Voraussetzungen für mehrere gleichartige Strafen erfüllt, zu der Strafe der schwersten Straftat verurteilt und die Strafe angemessen erhöht. Das Gericht darf jedoch das Höchstmass der angedrohten Strafe nicht um mehr als die Hälfte erhöhen. Dabei ist es an das gesetzliche Höchstmass gebunden.
4.4 Die Beschwerdeführerin weist darauf hin, dass der Beschwerdegegner gemäss den Angaben der Stadtpolizei Zürich am 3. November 2008 einen Ladendiebstahl verübt hat. Selbst wenn dies zutreffen und die Vorinstanz damit fälschlicherweise geschlossen haben sollte, der Beschwerdegegner sei seit Ende 2007 nicht mehr deliktisch in Erscheinung getreten, was für seinen positiven Lebenswandel spreche, führt dies nicht zur Gutheissung der Beschwerde. Denn diese kann nicht allein deshalb gutgeheissen werden, um die Verbesserung der Begründung der Strafzumessung zu veranlassen, wenn die ausgesprochene Strafe im Ergebnis vor Bundesrecht standhält (siehe <ref-ruling> E. 2c). Dies ist vorliegend der Fall. Es ist darauf hinzuweisen, dass die Vorinstanz einerseits bereits die weitere Delinquenz des Beschwerdegegners trotz laufendem Verfahren ausdrücklich erheblich straferhöhend gewichtet. Andererseits konnte die Vorinstanz angesichts der erfolgreich abgeschlossenen deliktsorientierten Therapie willkürfrei auf einen positiven Wandel im Leben des Beschwerdegegners schliessen und diesen Aspekt in geringem Mass strafmindernd einbeziehen.
Darüber hinaus bringt die Beschwerdeführerin nicht vor, dass die Vorinstanz wesentliche Gesichtspunkte ausser Acht gelassen oder rechtlich nicht massgebende Kriterien angewendet hätte, sondern rügt einzig, sie habe - ausgehend von den grundsätzlich korrekt festgestellten Tat- und Täterkomponenten - die Strafe zu tief angesetzt. Bei der Gewichtung der verschiedenen Strafzumessungsfaktoren steht dem urteilenden Gericht, wie dargelegt, ein Ermessensspielraum zu. Der Schluss der Vorinstanz auf ein (bloss) mittelschweres Verschulden des Beschwerdegegners verletzt kein Bundesrecht. Ebenso wenig ist die Folgerung unhaltbar, die übrigen Tatbestände fielen verglichen mit den schwersten Straftaten (Raub bzw. bandenmässiger Diebstahl) weniger ins Gewicht. Ferner verkennt die Vorinstanz nicht, dass der Beschwerdegegner erst aufgrund der ihn belastenden Beweise ein Teilgeständnis abgelegt hat, weshalb sie diesen Umstand auch nur leicht strafmindernd berücksichtigt. Schliesslich begründet sie explizit, weshalb sie die Strafe im Ergebnis tiefer ansetzt als das Bezirksgericht. So weist sie zutreffend darauf hin, die erste Instanz habe in ihrem Urteil vom 3. Oktober 2008 zu Unrecht ihr Urteil vom 7. September 2007 in gleicher Sache unter dem Titel Vorstrafen straferhöhend in die Strafzumessung einbezogen, obwohl der Beschwerdegegner sämtliche zu beurteilenden Taten vor dem Zeitpunkt der ersten Urteilsfällung begangen hat (Deliktszeitraum März 2003 bis Juni 2007).
III. Kosten- und Entschädigungsfolgen
5. Die Beschwerde der Oberstaatsanwaltschaft (Verfahren 6B_104/2010) ist abzuweisen. Der Beschwerdeführerin sind keine Gerichtskosten aufzuerlegen (<ref-law>).
Die Beschwerde von X._ (Verfahren 6B_125/2010) ist abzuweisen. 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 der Oberstaatsanwaltschaft (Verfahren 6B_104/2010) wird abgewiesen.
2. Die Beschwerde von X._ (Verfahren 6B_125/2010) wird abgewiesen.
3. Das Gesuch von X._ um unentgeltliche Rechtspflege (Verfahren 6B_125/2010) wird abgewiesen.
4. Die Gerichtskosten von Fr. 800.-- (Verfahren 6B_125/2010) werden X._ auferlegt.
5. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, I. Strafkammer, schriftlich mitgeteilt.
Lausanne, 6. April 2010
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Favre Stohner