Sachverhalt: A. Y._ und X._ heirateten im Jahre 2004. Sie haben zwei Söhne, A._ (Jahrgang 2004) und B._ (Jahrgang 2006). Der Vizepräsident des Bezirksgerichts Frauenfeld erliess am 26. März 2009 eine Eheschutzverfügung. Die gemeinsamen Kinder wurden unter die elterliche Obhut von Y._ gestellt. X._ wurde ein wöchentliches Besuchs- und ein Ferienbesuchsrecht eingeräumt. Am 19. August 2010 holte X._ seine Kinder ab. Anstatt sie wie vereinbart am 22. August 2010 zurückzubringen, reiste er mit ihnen nach Gandoubah/Tunesien, wo sie seither leben. B. Das Bezirksgericht Winterthur sprach X._ am 19. Januar 2012 der mehrfachen qualifizierten Freiheitsberaubung und Entführung, des mehrfachen Entziehens von Unmündigen sowie der versuchten Erpressung schuldig. Das Verfahren betreffend Drohung stellte es ein. Das Bezirksgericht bestrafte X._ mit einer Freiheitsstrafe von acht Jahren. Es verpflichtete ihn, Y._ eine Genugtuung von Fr. 30'000.-- zu bezahlen. Zudem wurde X._ dem Grundsatz nach verpflichtet, seiner Ehefrau Schadenersatz sowie den Kindern Schadenersatz und Genugtuung zu leisten. In teilweiser Gutheissung der Berufung von X._ erkannte das Obergericht des Kantons Zürich am 10. September 2012 auf eine Freiheitsstrafe von sechs Jahren unter Anrechnung der Untersuchungshaft und des vorzeitigen Strafvollzugs von 693 Tagen. Zugleich stellte es insbesondere fest, dass der erstinstanzliche Entscheid im Schuldpunkt (mehrfache qualifizierte Freiheitsberaubung und Entführung, mehrfaches Entziehen von Unmündigen sowie versuchte Erpressung) in Rechtskraft erwachsen war. X._ wurde verpflichtet, Y._ eine Genugtuung von Fr. 30'000.-- und dem Grundsatz nach Schadenersatz zu leisten. Die Schadenersatz- und Genugtuungsbegehren der beiden Kinder verwies das Obergericht auf den Weg des Zivilprozesses. C. X._ führt Beschwerde in Strafsachen. Er beantragt im Wesentlichen, die vorinstanzlichen Urteile seien aufzuheben. Es sei festzustellen, dass seine Verhaftung völkerrechtswidrig erfolgt sei, und er sei aus dem Freiheitsentzug zu entlassen. Eventualiter sei er mit einer Freiheitsstrafe von zwei Jahren zu bestrafen. Für die rechtswidrigen respektive ungerechtfertigten Zwangsmassnahmen sei er angemessen zu entschädigen. Zudem ersucht er um Gewährung der unentgeltlichen Verbeiständung. 