Sachverhalt:
A. Das Bezirksgericht Zürich verurteilte X._ am 4. Dezember 2008 wegen mehrfachen Menschenhandels im Sinne von Art. 182 Abs. 1 und 2 StGB und mehrfacher Widerhandlung gegen Art. 23 Abs. 1 al. 4 und 5 sowie Art. 23 Abs. 2 ANAG zu einer Freiheitsstrafe von 3 1⁄2 Jahren und einer Geldstrafe von 60 Tagessätzen zu Fr. 20.--.
Die gegen dieses Urteil erhobene Berufung der Staatsanwaltschaft im Strafpunkt und die Anschlussberufung von X._ wies das Obergericht des Kantons Zürich am 15. September 2009 ab.
B. Die Oberstaatsanwaltschaft des Kantons Zürich gelangt mit Beschwerde in Strafsachen an das Bundesgericht. Sie beantragt, das Urteil vom 15. September 2009 in Bezug auf die ausgefällte Strafe aufzuheben und entweder eine höhere Strafe zu verhängen oder die Sache zur Ausfällung einer höheren Strafe an die Vorinstanz zurückzuweisen.
C. Das Obergericht des Kantons Zürich verzichtet auf eine Stellungnahme zur Beschwerde. X._ lässt sich innert der angesetzten Frist nicht vernehmen. Sein Schreiben vom 3. Februar 2010 erfolgt verspätet und hat im vorliegenden Verfahren unberücksichtigt zu bleiben.

Erwägungen:
1. Dem angefochtenen Entscheid liegt folgende Sachverhaltsfeststellung zugrunde:
1.1 Der Beschwerdegegner beutete die drei aus Bulgarien stammenden Frauen A._, B._ und C._ je während mehrerer Monate aus, indem er sie als Prostituierte für sich arbeiten liess und aus ihrer Tätigkeit erhebliche finanzielle Einkünfte erwirtschaftete. A._ arbeitete während rund 4 Monaten für den Beschwerdegegner. Er nahm ihr mindestens Fr. 5'000.-- ihres Verdienstes ab und liess sie zudem die Miete für eine Wohnung in E._ bezahlen. Die Tätigkeit von B._ erstreckte sich ebenfalls über ungefähr 4 Monate, wobei sie dem Beschwerdegegner jeweils mindestens 50 % ihrer Einkünfte abgeben musste. C._ wurde vom Beschwerdegegner während rund 8 Monaten ausgebeutet. Er führte die damals 18-Jährige in die Prostitution ein, wobei sie ihm teilweise ihren gesamten Tagesverdienst, teilweise 50 % davon abgeben sowie eine einmalige Zahlung von Fr. 5'000.-- leisten musste. Im März 2007 trat er C._ an D._ ab, welchem sie 50 % ihrer Einkünfte abliefern musste. D._ versprach dem Beschwerdegegner im Gegenzug den Erlass einer Schuld von Fr. 5'000.--. Für die Vermittlung von A._ und C._ an ein Sexetablissement in Basel erhielt der Beschwerdegegner zudem ein Darlehen von Fr. 5'000.--. Die beiden Frauen musste er als Pfand für seine Schuld im betreffenden Etablissement zurücklassen. Mit A._ und B._ unterhielt der Beschwerdeführer eine vermeintliche Liebesbeziehung.
Der in Bulgarien wohnhafte Beschwerdeführer überredete die drei Geschädigten, in der Schweiz einer Tätigkeit als Prostituierte nachzugehen, wozu sich diese aufgrund ihrer finanziellen Notlage bzw. aus Zuneigung zum Beschwerdegegner bereit erklärten. In der Folge übernahm er die Kontrolle über ihre Prostitutionstätigkeit und bestimmte ihren Arbeitsort. Er vermittelte sie an diverse Sexetablissements und fuhr sie während seiner Aufenthalte in der Schweiz jeweils auch zu ihrem Arbeitsort. Die Geschädigten wurden ständig überwacht und kontrolliert. Sie mussten dem Beschwerdegegner zum Teil mehrmals täglich Auskunft über ihre Einkünfte geben. Er hielt die Frauen, teilweise trotz Schmerzen, an, möglichst viel zu arbeiten. Dabei schreckte er auch vor Drohungen, Demütigungen und körperlicher Züchtigung nicht zurück. Die durch die vermeintliche Liebesbeziehung bestehende Abhängigkeit nutzte er systematisch aus. Nachdem sich A._ und C._ vom Beschwerdegegner gegen dessen Willen getrennt hatten, reiste dieser am 9. Juli 2007 in die Schweiz und versuchte mit den beiden Frauen Kontakt aufzunehmen, um wieder die Kontrolle über sie zu erlangen, was ihm jedoch aufgrund seiner Verhaftung am gleichen Tag nicht gelang.
1.2 Der Beschwerdegegner reiste wiederholt in die Schweiz und hielt sich hier vom 6. Dezember 2006 bis 28. Februar 2007 sowie verschiedentlich in den Monaten März bis Mai 2007 auf, um seiner Tätigkeit im Prostitutionsgewerbe nachzugehen. Zudem brachte er die drei Geschädigten in die Schweiz und sorgte hier für ihre Unterkunft, damit sie ihre Tätigkeit als Prostituierte ausüben konnten. Dies obschon sowohl der Beschwerdegegner als auch die Geschädigten weder über ein entsprechendes Visum noch eine fremdenpolizeiliche Aufenthalts- bzw. Arbeitsbewilligung verfügten (Urteil des Bezirksgerichts S. 14 f.).
2. 2.1 Die Beschwerdeführerin wendet sich ausschliesslich gegen die Strafzumessung. Sie rügt, die ausgesprochene Strafe sei zu milde ausgefallen.
2.2 Nach Art. 182 Abs. 1 Satz 1 StGB wird mit Freiheitsstrafe oder Geldstrafe bestraft, wer als Anbieter, Vermittler oder Abnehmer mit einem Menschen Handel treibt zum Zwecke der sexuellen Ausbeutung. Das Anwerben eines Menschen zu diesen Zwecken ist dem Handel gleichgestellt (Art. 182 Abs. 1 Satz 2 StGB). Handelt der Täter gewerbsmässig, so ist die Strafe Freiheitsstrafe nicht unter einem Jahr (Art. 182 Abs. 2 StGB). In jedem Fall ist auch eine Geldstrafe auszusprechen (Art. 182 Abs. 3 StGB).
Wer rechtswidrig das Land betritt oder darin verweilt bzw. im In- oder Ausland die rechtswidrige Ein- oder Ausreise oder das rechtswidrige Verweilen im Lande erleichtert oder vorbereiten hilft, wird mit Geldstrafe bis zu 180 Tagessätzen bestraft (Art. 23 Abs. 1 al. 4 und 5 des bis am 31. Dezember 2007 geltenden Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer, ANAG; BS 1 121). Wer in der Absicht, sich oder einen anderen unrechtmässig zu bereichern, einem Ausländer die rechtswidrige Einreise oder das rechtswidrige Verweilen im Lande erleichtert oder vorbereiten hilft, wird mit Freiheitsstrafe bis zu drei Jahren oder Geldstrafe bestraft. Mit der Freiheitsstrafe ist eine Geldstrafe zu verbinden (Art. 23 Abs. 2 ANAG).
Hat der Täter durch eine oder mehrere Handlungen die Voraussetzungen für mehrere gleichartige Strafen erfüllt, so verurteilt ihn das Gericht gemäss Art. 49 Abs. 1 Satz 1 StGB zu der Strafe der schwersten Straftat und erhöht sie angemessen. Das Gericht ist verpflichtet, diesen Strafschärfungsgrund mindestens straferhöhend zu berücksichtigen (<ref-ruling> E. 8.1 mit Hinweisen). Dabei ist es an das gesetzliche Höchstmass der Strafart gebunden (Art. 49 Abs. 1 Satz 3 StGB).
2.3 Das Gericht misst die Strafe nach dem Verschulden des Täters zu. Es berücksichtigt das Vorleben und die persönlichen Verhältnisse sowie die Wirkung der Strafe auf das Leben des Täters (Art. 47 Abs. 1 StGB). Das Verschulden wird 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, wie weit der Täter nach den inneren und äusseren Umständen in der Lage war, die Gefährdung oder Verletzung zu vermeiden (Art. 47 Abs. 2 StGB). Die Strafrechtliche Abteilung des Bundesgerichts greift auf Beschwerde in Strafsachen hin nur ein, wenn die Vorinstanz den gesetzlichen Strafrahmen über- oder unterschritten hat, wenn sie von rechtlich nicht massgebenden Kriterien ausgegangen ist oder wesentliche Gesichtspunkte ausser Acht gelassen bzw. durch Überschreitung oder Missbrauch ihres Ermessens falsch gewichtet hat (<ref-ruling> E. 5.3.1; <ref-ruling> E. 2.1; <ref-ruling> E. 6.1).
3. Die Vorinstanz erwägt zur Strafzumessung, das objektive Tatgewicht sei als erheblich einzustufen. Ebenfalls schwer wiege das subjektive Verschulden (angefochtener Entscheid S. 6). Der Beschwerdegegner habe aus rein finanziellen Motiven gehandelt. Sein Ziel sei es gewesen, möglichst viel Kapital aus den drei Geschädigten zu schlagen. Hierbei sei er mit grosser Hartnäckigkeit und ohne Rücksicht auf deren Befinden vorgegangen. Stark straferhöhend würden sich die Tatmehrheit und die mehrfache Tatbegehung auswirken. Mit Urteil vom 21. Mai 2004 sei der Beschwerdegegner auch vom Berufungsgericht Nîmes wegen mehrfacher schwerer Zuhälterei zu einer unbedingten Freiheitsstrafe von 5 Jahren verurteilt worden. Erst am 1. Mai 2005 sei er in Frankreich nach 2 1⁄2 Jahren aus dem Strafvollzug entlassen worden. Nur 1 1⁄2 Jahre später habe er angefangen, in ähnlicher Manier auch in der Schweiz zu delinquieren. Die einschlägige Vorstrafe sei stark straferhöhend zu berücksichtigen. Hingegen sei zugunsten des Beschwerdegegners zu vermerken, dass er sich gemäss den Führungsberichten des Gefängnisses Horgen und der Strafanstalt Pöschwies in der Haft vorbildlich verhalten habe. Der Umstand, dass der vor dem Bezirksgericht noch nicht geständige Beschwerdegegner den erstinstanzlichen Schuldspruch akzeptiert habe, sei als konkludentes Geständnis im Berufungsverfahren auszulegen und leicht strafmindernd anzurechnen (angefochtener Entscheid S. 7). Die Freiheitsstrafe von 3 1⁄2 Jahren erscheine angemessen. Die von der Staatsanwaltschaft zur Begründung der Straferhöhung angeführten Umstände seien im Wesentlichen bereits dem Tatbestand des qualifizierten Menschenhandels inhärent, welcher deshalb auch einen entsprechenden Strafrahmen vorsähe. Die ausgefällte Strafe erweise sich auch im Vergleich mit ähnlichen Fällen keineswegs als zu tief (angefochtener Entscheid S. 8).
4. 4.1 Das durch den Tatbestand des Menschenhandels zu erfassende Unrecht besteht in der Ausnützung einer Machtposition durch den Täter und einer Verletzung des sexuellen Selbstbestimmungsrechts des Opfers (<ref-ruling> E. 3.1; <ref-ruling> E. 1c; Botschaft vom 11. März 2005 über die Genehmigung des Fakultativprotokolls vom 25. Mai 2000 zum Übereinkommen über die Rechte des Kindes, betreffend den Verkauf von Kindern, die Kinderprostitution und die Kinderpornografie, und über die entsprechende Änderung der Strafnorm über den Menschenhandel; BBl 2005 2834). Nach Art. 182 StGB strafbar macht sich auch, wer nur einen Menschen oder nur einmal mit einem oder mehreren Menschen handelt (BBl 2005 2835). Der Täter handelt gewerbsmässig, wenn aus den gesamten Umständen geschlossen werden muss, dass er sich darauf eingerichtet hat, durch deliktische Handlungen relativ regelmässige Einnahmen zu erzielen, die einen namhaften Beitrag an die Kosten zur Finanzierung seiner Lebensgestaltung darstellen (<ref-ruling> E. 3a; <ref-ruling> E. 4c). Gewerbsmässigkeit im Sinne von Art. 182 Abs. 2 StGB ist regelmässig mit einer Mehrzahl von Opfern und einer beachtlichen Deliktssumme verbunden (BBl 2005 2836).
4.2 Die Vorinstanz geht zutreffend von einem oberen Strafrahmen von 20 Jahren Freiheitsstrafe aus (Art. 182 Abs. 1, Art. 40, Art. 49 Abs. 1 Satz 3 StGB). Da der Beschwerdegegner gewerbsmässig handelte, liegt der untere Strafrahmen bei einer Freiheitsstrafe nicht unter einem Jahr (Art. 182 Abs. 2 StGB). Ist, wie vorliegend, zusätzlich zur Freiheitsstrafe zwingend auch eine Geldstrafe auszusprechen (vgl. Art. 182 Abs. 3 StGB und Art. 23 Abs. 2 Satz 2 ANAG), muss der Geldstrafe bei der Bemessung der Freiheitsstrafe Rechnung getragen werden, damit die sich aus Freiheitsstrafe und Geldstrafe zusammensetzende Gesamtstrafe die schuldangemessene Sanktion nicht übersteigt (vgl. <ref-ruling> E. 4.5.2).
5. 5.1 Vorliegend ist sowohl objektiv als auch subjektiv von einem schweren Verschulden auszugehen. Bei der Beurteilung der objektiven Tatschwere ist zu berücksichtigen, dass der Beschwerdegegner die drei Frauen je über den verhältnismässig langen Zeitraum von 4 bzw. 8 Monaten intensiv der Prostitution zuführte. Durch die ständige Überwachung waren die Frauen nicht nur in ihrer sexuellen Selbstbestimmung, sondern auch massgeblich in ihrer Handlungsfreiheit beschränkt. Erschwerend wirkt sich aus, dass er den Geschädigten teilweise ihre gesamten, zumindest jedoch einen sehr erheblichen Teil ihrer Einkünfte abnahm und dass er auch Drohungen sowie physische Gewalt einsetzte und die Gefühle der Frauen für ihn bewusst ausnutzte, um sie gefügig zu machen. Besonders ins Gewicht fällt, dass der Beschwerdegegner auch vor massiven körperlichen Übergriffen nicht zurückschreckte, wenn sich die Frauen ihm nicht fügen wollten, und die Geschädigten zum Teil trotz Schmerzen und gesundheitlicher Probleme zur Prostitution zwang und sie immer wieder anhielt, möglichst viel zu arbeiten. So verlangte er beispielsweise von B._, dass sie bereits wenige Tage nachdem sie sich anfangs Dezember 2006 einem medizinischen Eingriff wegen einer Bauchhöhlenschwangerschaft unterziehen musste, ihre Prostitutionstätigkeit wieder aufnehmen müsse, und wies sie an, bei Bedarf Schmerztabletten zu konsumieren. B._ und C._ verprügelte er einmal dermassen, indem er mit den Fäusten auf sie einschlug und mit den Füssen gegen sie trat, dass sie Verletzungen davon trugen. In subjektiver Hinsicht handelte der Beschwerdegegner ausgesprochen skrupellos und egoistisch, ohne Rücksicht auf das Befinden der Geschädigten, um sich seinen Lebensunterhalt in der Schweiz und in Bulgarien finanzieren zu können.
5.2 Die Beschwerdeführerin bringt vor, die Vorinstanz habe die Tragweite des Doppelverwertungsverbots verkannt (Beschwerde S. 6). Das sog. Doppelverwertungsverbot besagt, dass Umstände, die zur Anwendung eines höheren bzw. tieferen Strafrahmens führen, innerhalb des geänderten Strafrahmens nicht noch einmal als Straferhöhungs- oder Strafminderungsgrund berücksichtigt werden dürfen. Indessen darf der Richter zusätzlich berücksichtigen, in welchem Ausmass ein qualifizierender oder privilegierender Tatumstand gegeben ist. Der Richter verfeinert damit nur die Wertung, die der Gesetzgeber mit der Festsetzung des Strafrahmens vorgezeichnet hat (<ref-ruling> E. 2b; <ref-ruling> E. 2b). Die Opfermehrheit, die Dauer und Intensität der Tätigkeit sowie die Höhe des deliktischen Gewinns wirken sich beim Tatbestand des Menschenhandels daher regelmässig nicht nur auf die rechtliche Qualifikation der gewerbsmässigen Tatbegehung, sondern auch auf das Strafmass aus. Das Ausmass des gewerbsmässigen Menschenhandels ist bei der Strafzumessung mitunter auch unter Verschuldensgesichtspunkten zu würdigen. Die Vorinstanz trug diesem Umstand in Verletzung von Art. 47 StGB jedenfalls nicht genügend Rechnung.
Der Tatbestand des Menschenhandels ist gemäss der bundesgerichtlichen Rechtsprechung in der Regel erfüllt, wenn junge Frauen, die aus dem Ausland kommen, unter Ausnützung ihrer schwierigen Lage zur Ausübung der Prostitution in der Schweiz engagiert werden. Ihre "Einwilligung" in diese Tätigkeit und in die (illegale) Überführung in die Schweiz ist nicht wirksam, wenn sie auf ihre schwierigen wirtschaftlichen Verhältnisse im Herkunftsland zurückzuführen ist. Die Personen verfügen in diesen Fällen nicht über die erforderliche Entscheidungsfreiheit (vgl. <ref-ruling> E. 3.1; <ref-ruling> E. 4b und c). Wendet der Täter über die Ausnutzung der Notlage des Opfers hinaus weitere Druckmittel wie physische Gewalt und Drohungen an, ist dies bei der Strafzumessung ebenfalls erheblich erschwerend zu gewichten. Eine unzulässige Doppelverwertung ist auch insoweit zu verneinen.
5.3 Stark straferhöhend muss sich auswirken, worauf auch die Vorinstanz hinweist, dass der Beschwerdegegner in Frankreich bereits einschlägige Vorstrafen verbüsste (vgl. <ref-ruling> E. 2d/cc; <ref-ruling> E. 2). Besonders ins Gewicht fällt hierbei, dass der Beschwerdegegner nur kurze Zeit nachdem er in Frankreich 2 1⁄2 Jahre seiner Strafe verbüsst hatte und im Mai 2005 aus dem Strafvollzug entlassen worden war, sich in der Schweiz auf ähnliche Weise erneut strafbar machte. Ein solches Verhalten zeugt von einer ausserordentlichen Uneinsichtigkeit und Unbelehrbarkeit. Straferhöhend zu berücksichtigen ist sodann die Deliktsmehrheit, da sich der Beschwerdegegner auch der mehrfachen Widerhandlung gegen Art. 23 Abs. 1 al. 4 und 5 sowie Abs. 2 ANAG schuldig machte (vgl. Art. 49 Abs. 1 StGB; <ref-ruling> E. 8.1 mit Hinweisen).
5.4 Geständnisse können grundsätzlich strafmindernd berücksichtigt werden, namentlich wenn sie Ausdruck von Einsicht und Reue des Täters sind (vgl. <ref-ruling> E. 2d; <ref-ruling> E. 2d). Ein Verzicht auf Strafminderung kann sich demgegenüber aufdrängen, wenn das Geständnis die Strafverfolgung nicht erleichtert hat, namentlich weil der Täter nur aufgrund einer erdrückenden Beweislage oder gar erst nach Ausfällung des erstinstanzlichen Urteils geständig geworden ist. Kein eine Strafreduktion rechtfertigendes Geständnis kann gemäss der bundesgerichtlichen Rechtsprechung in der Nichtanfechtung der Schuldsprüche erblickt werden (Urteil des Bundesgerichts 6S.531/ 2006 vom 24. Januar 2007 E. 3.6.3 mit Hinweisen). Der Beschwerdegegner bestritt seine Taten im Untersuchungsverfahren und im erstinstanzlichen Verfahren fast vollumfänglich und bezeichnete die ihn belastenden Beweismittel als falsch, fehlerhaft oder erlogen (vgl. Urteil des Bezirksgerichts S. 6 und 23). Dass er gegen das Urteil des Bezirksgerichts selber kein Rechtsmittel einlegte bzw. nur im zulässigen Umfang Anschlussberufung erhob (vgl. § 416 Abs. i.V.m. Art. 413 Abs. 1 der Strafprozessordnung des Kantons Zürich vom 4. Mai 1919), kann ihm im Berufungsverfahren nicht zugutegehalten werden. Indem die Vorinstanz dies als konkludentes Geständnis im Berufungsverfahren auslegt und, wenn auch nur leicht, strafmindernd wertet, verletzt sie Bundesrecht.
5.5 Nicht ersichtlich ist sodann, unter welchen Gesichtspunkten die gute Führung des Beschwerdegegners in der Untersuchungshaft und im vorzeitigen Strafvollzug bei der Strafzumessung zu seinen Gunsten berücksichtigt werden kann. Zwar ist für die Strafzumessung grundsätzlich auch das Verhalten des Täters nach der Tat von Bedeutung, soweit dieses Rückschlüsse auf den Täter und seine Einstellung zur Tat zulässt (Urteil des Bundesgerichts 6S.348/2004 vom 20. Januar 2005 E. 4.1). Strafmindernd im Sinne eines entlastenden Nachtatverhaltens wirken vor allem das Bekunden von Einsicht und Reue (<ref-ruling> E. 2d/cc). Ein korrektes Verhalten in der Untersuchungshaft und im Strafvollzug kann demgegenüber vorausgesetzt werden. Sein vorbildliches Verhalten im (vorzeitigen) Strafvollzug wird dem Beschwerdegegner in erster Linie bei der Frage nach der bedingten Entlassung zugutezuhalten sein (vgl. Art. 86 StGB). Es kann hingegen im Rahmen der Strafzumessung nicht als besondere Einsicht oder Reue interpretiert werden. Die Vorinstanz überschritt auch in diesem Punkt ihr Ermessen.
6. Im Ergebnis ist die Freiheitsstrafe von 3 1⁄2 Jahren, unter Berücksichtigung der Geldstrafe von 60 Tagessätzen, angesichts der objektiven Tatschwere (Opfermehrheit, relativ lange und intensive Deliktsdauer, Höhe des deliktischen Erlöses, Einsatz von körperlicher Gewalt, Drohungen und Ausnutzung der Liebesbeziehung als Druckmittel), des ausgesprochen skrupellosen, egoistischen und rücksichtslosen Vorgehens des Beschwerdegegners, der nur kurze Zeit zurückliegenden, einschlägigen Vorstrafen sowie der Deliktsmehrheit, unzulässig milde. Der angefochtene Entscheid ist aufzuheben und die Sache zur neuen Strafzumessung an die Vorinstanz zurückzuweisen.
7. Die Beschwerdeführerin rügt, die Vorinstanz verweise bei der Begründung der Strafzumessung auf vergleichbare Fälle, ohne diese zu benennen, was nicht angehe (Beschwerde S. 7).
Die Rüge ist begründet. Die in verschiedenen Fällen verhängten Strafen sind gerade beim sehr weit gefassten Tatbestand des Menschenhandels nur beschränkt vergleichbar, da von den konkreten Tatumständen abhängig. Stützt sich das Gericht auf Vergleichsurteile, muss es diese benennen und sich mit dem Argument auch auseinandersetzen, ansonsten es seine Begründungspflicht (vgl. Art. 50 StGB; BGE <ref-ruling> E. 2.1) verletzt.
8. Die Beschwerde ist gutzuheissen. Dem Beschwerdegegner sind keine Gerichtskosten aufzuerlegen, da er im bundesgerichtlichen Verfahren keine Anträge stellte (Art. 66 Abs. 1 BGG). Der obsiegenden Beschwerdeführerin ist keine Entschädigung auszurichten (Art. 68 Abs. 3 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, das Urteil des Obergerichts des Kantons Zürich vom 15. September 2009 aufgehoben und die Angelegenheit zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2. Es werden keine Kosten erhoben und keine Entschädigung ausgerichtet.
3. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Strafkammer, schriftlich mitgeteilt.
Lausanne, 18. Februar 2010
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Favre Unseld