Sachverhalt:
A. Y._ (geb. 1986) und X._ (geb. 1984) heirateten im Jahr 2004. Der Ehe entsprossen die gemeinsamen Kinder A._ (geb. 2005) und B._ (geb. 2007).
Die Trennung erfolgte am 9. August 2011.
Die Ehefrau leitete am 22. August 2011 vor dem Richteramt Olten-Gösgen ein Eheschutzverfahren ein. Mit Verfügung vom 20. September 2011 räumte die Amtsgerichtspräsidentin dem Ehemann für die Dauer des Verfahrens zwei Mal pro Monat ein begleitetes Besuchsrecht betreffend die beiden Kinder ein. Weiter errichtete sie eine Beistandschaft gemäss <ref-law> und beauftragte den Beistand mit der Organisation und Durchführung des begleiteten Besuchsrechts.
Am 16. November 2011 bestätigte die Amtsgerichtspräsidentin die bereits am 20. September 2011 getroffene einstweilige Obhuts- und Besuchsrechtsregelung. Sodann gab sie mit Blick auf die Zuteilung der Obhut einen Bericht bei der Familienberatung Olten-Gösgen in Auftrag.
Mit dringlichem Beschluss vom 9. Dezember 2011 entzog die Vormundschaftsbehörde der Sozialregion Olten beiden Eltern die elterliche Obhut (Ziff. 1) und ordnete (über die Organisation "Kompass") die Unterbringung der Kinder an einem Pflegeplatz an (Ziff. 2); ausserdem sei den Eltern abwechselnd zwei Mal monatlich ein begleitetes Besuchsrecht einzuräumen (Ziff. 3). Am 13. Dezember 2011 änderte die Vormundschaftsbehörde die vorerwähnte Ziffer 2 insofern ab, als sie die provisorische Unterbringung der Kinder bei der Familie C._, einer Tante der Kinder, anordnete. Die Amtsgerichtspräsidentin bestätigte diese Anordnungen am 22. Dezember 2011.
Nach Eingang des Berichts entschied die Amtsgerichtspräsidentin, soweit vorliegend relevant, mit Verfügung vom 24. Februar 2012, die beiden Kinder für die Dauer des Getrenntlebens unter die Obhut der Mutter zu stellen (Ziff. 6), gewährte dem Vater einmal monatlich ein begleitetes Besuchsrecht von drei Stunden (Ziff. 7) und beauftragte den Beistand mit der Umplatzierung der Kinder zur Mutter, mit den diesbezüglichen organisatorischen Vollzugsmassnahmen sowie mit der anschliessenden sozialpädagogischen Erziehungsunterstützung der Mutter (Ziff. 8)
B. Gegen die vorstehend erwähnten Ziffern der Verfügung der Amtsgerichtspräsidentin ergriff der Ehemann Berufung an das Obergericht des Kantons Solothurn; er beantragte im Wesentlichen die Einholung eines kinderpsychiatrischen Gutachtens, einstweilen ein unbegleitetes Besuchsrecht und alsdann die Zuteilung der Obhut über die beiden Kinder an ihn. Mit Urteil vom 25. Mai 2012 wies das Obergericht die Berufung ab, soweit sie nicht gegenstandslos geworden war.
C. Hiergegen gelangt X._ (nachfolgend: Beschwerdeführer) mit Beschwerde in Zivilsachen vom 28. Juni 2012 an das Bundesgericht und verlangt im Wesentlichen die Zuteilung der Obhut über die beiden Kinder.
Im Rahmen der Stellungnahme zum Gesuch um aufschiebende Wirkung des Beschwerdeführers machte die Beschwerdegegnerin geltend, der Beschwerdeführer habe die Kinder nach Erhalt des angefochtenen Entscheids entführt und vermutlich in die Türkei verbracht, weshalb er - unter Androhung von <ref-law> - anzuweisen sei, die Kinder zurückzubringen bzw. dem Vormundschaftsamt Olten zu übergeben.
Die Präsidentin der II. zivilrechtlichen Abteilung wies das Gesuch um aufschiebende Wirkung ab und trat auf das Gesuch um Kindesrückschaffung nicht ein (Verfügung vom 10. Juli 2012).
Es wurden die Akten, in der Sache aber keine Vernehmlassungen eingeholt.
Mit Verfügungen vom 19. Juli 2012 und vom 20. Juli 2012 hat das Obergericht des Kantons Solothurn die Rechtsvertreterin des Beschwerdeführers aufgefordert, bis zum 2. August 2012 dessen Adresse mitzuteilen.
Mit Schreiben vom 14. August 2012 teilte die Rechtsvertreterin dem Obergericht mit, sie könne die aktuelle Adresse des Beschwerdeführers nicht bekannt geben, da der Kontakt zu ihm abgebrochen sei. Sodann teilte sie dem Obergericht mit Schreiben vom 17. August 2012 mit, sie habe das Mandat niedergelegt.

Erwägungen:
1. 1.1 Angefochten ist ein kantonal letztinstanzlicher Eheschutzentscheid, der u.a. die Obhutszuteilung regelt; die Beschwerde in Zivilsachen steht somit unabhängig von einem Mindeststreitwert offen (Art. 72 Abs. 1, Art. 75 Abs. 2 und Art. 90 BGG).
1.2 Nach der Rechtsprechung gelten Eheschutzentscheide als vorsorgliche Massnahmen im Sinne von <ref-law> (<ref-ruling> E. 5.1 und 5.2 S. 396 f.). Daher kann in der Beschwerde nur die Verletzung verfassungsmässiger Rechte gerügt werden (s. dazu <ref-ruling> E. 4.1 S. 588). Auch eine Berichtigung oder Ergänzung der Sachverhaltsfeststellungen kommt nur dann in Frage, wenn die kantonale Instanz verfassungsmässige Rechte verletzt hat (<ref-ruling> E. 4.1 S. 588). Für alle Vorbringen betreffend die Verletzung verfassungsmässiger Rechte gilt das strenge Rügeprinzip (<ref-law>). Die rechtssuchende Partei muss präzise angeben, welches verfassungsmässige Recht durch den angefochtenen kantonalen Entscheid verletzt wurde, und im Einzelnen darlegen, worin die Verletzung besteht (<ref-ruling> E. 3.2 S. 444). Das Bundesgericht prüft nur klar und detailliert erhobene und, soweit möglich, belegte Rügen. Auf ungenügend begründete Rügen und rein appellatorische Kritik am angefochtenen Entscheid tritt es nicht ein (<ref-ruling> E. 2.2 S. 246; <ref-ruling> E. 3.1 S. 399 f.).
1.3 Gemäss <ref-law> dürfen neue Tatsachen und Beweismittel nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt. Das Vorbringen von Tatsachen oder Beweismitteln, die sich zwar auf das vorinstanzliche Prozessthema beziehen, jedoch erst nach dem angefochtenen Entscheid zutage getreten oder entstanden sind (sog. "echte" Noven), kann aber von vornherein nicht durch das weitergezogene Urteil veranlasst worden sein und ist im bundesgerichtlichen Verfahren unzulässig (<ref-ruling> E. 5.2.4 S. 229; <ref-ruling> E. 2.1 S. 343 f.). Daraus folgt, dass die vom Beschwerdeführer eingereichten Beweismittel, die sich auf einen Sachverhalt beziehen, der sich erst nach dem vorinstanzlichen Entscheid zugetragen hat, vom Bundesgericht nicht berücksichtigt werden können.
1.4 Ob die Kinder nach Fällung des angefochtenen Entscheids tatsächlich in die Türkei verbracht und dort einen neuen Aufenthalt begründet haben, kann offen bleiben, denn selbst wenn dies der Fall wäre, bliebe die Zuständigkeit des Bundesgerichts erhalten (<ref-ruling> E. 2.3.2 S. 592 mit Hinweisen). Damit erweist sich das Fehlen einer aktuellen Adresse des Beschwerdeführers, worauf die Vorinstanz das Bundesgericht hinweist, als rechtlich nicht erheblich, so dass auch eine Aufforderung zur Bezeichnung einer Adresse des (anwaltlich vertretenen) Beschwerdeführers nach Massgabe von <ref-law> zu unterbleiben hat (Urteil 1C_180/2007 vom 12. Oktober 2007 E. 4).
2. Strittig ist vorliegend die Obhutszuteilung.
2.1 Das mit der "Regelung des Getrenntlebens" (Marginalie zu <ref-law>) befasste Eheschutzgericht trifft nach den Bestimmungen über die Wirkungen des Kindesverhältnisses die nötigen Massnahmen, wenn die Ehegatten unmündige Kinder haben (<ref-law>). Für die Zuteilung der Obhut an einen Elternteil gelten grundsätzlich die gleichen Kriterien wie im Scheidungsfall. Nach der Rechtsprechung hat das Wohl des Kindes Vorrang vor allen anderen Überlegungen, insbesondere vor den Wünschen der Eltern (zuletzt: Urteil 5A_905/2011 vom 28. März 2012 E. 2.1).
Vorab muss die Erziehungsfähigkeit der Eltern geklärt werden. Ist diese bei beiden Elternteilen gegeben, sind vor allem Kleinkinder und grundschulpflichtige Kinder demjenigen Elternteil zuzuteilen, der die Möglichkeit hat und dazu bereit ist, sie persönlich zu betreuen. Erfüllen beide Elternteile diese Voraussetzung ungefähr in gleicher Weise, kann die Stabilität der örtlichen und familiären Verhältnisse ausschlaggebend sein. Unter Umständen kann die Möglichkeit der persönlichen Betreuung auch dahinter zurücktreten (Urteil 5C.212/2005 vom 25. Januar 2006 E. 4.2 und 4.4.1, in: FamPra.ch 2006 S. 753 ff.). Schliesslich ist - je nach Alter der Kinder - ihrem eindeutigen Wunsch Rechnung zu tragen. Diesen Kriterien lassen sich die weiteren Gesichtspunkte zuordnen, namentlich die Bereitschaft eines Elternteils, mit dem anderen in Kinderbelangen zusammenzuarbeiten oder die Forderung, dass eine Zuteilung der Obhut von einer persönlichen Bindung und echter Zuneigung getragen sein sollte (vgl. <ref-ruling> E. 4a S. 209; <ref-ruling> E. 2 und 3 S. 319 ff.; <ref-ruling> E. 3 S. 354 f.; Urteil 5A_798/2009 vom 4. März 2010 E. 5.3; <ref-ruling> E. 5.3 S. 180 f.; Urteil 5A_905/2011 vom 28. März 2012 E. 2.1).
Bei der Beurteilung der für die Obhutszuteilung massgebenden Kriterien verfügt das Sachgericht über ein weites Ermessen (vgl. alle soeben zitierten Urteile). Auf Willkürbeschwerde hin kann das Bundesgericht deshalb nur eingreifen, wenn das Sachgericht grundlos von in Rechtsprechung und Lehre anerkannten Grundsätzen abgewichen ist, wenn es Gesichtspunkte berücksichtigt hat, die keine Rolle hätten spielen dürfen, oder wenn es umgekehrt rechtserhebliche Umstände ausser Acht gelassen hat. Der Ermessensentscheid muss sich als im Ergebnis offensichtlich unbillig, als in stossender Weise ungerecht erweisen (BGE 109 la 107 E. 2c S. 109; <ref-ruling> E. 4b S. 6 f.; <ref-ruling> E. 1 S. 99).
2.2 Die Vorinstanz hat namentlich unter Hinweis auf den eingeholten Bericht im Wesentlichen Folgendes erwogen:
Die Mutter sei erziehungsfähig, sie bedürfe aber intensiver sozialpädagogischer Unterstützung, da ihr Verhältnis zu den Kindern derzeit gestört sei. Zudem sei sie willens und in der Lage, die Kinder persönlich zu betreuen. Die Mutter sei auch bestrebt, den Zugang des anderen Elternteils zu den Kindern zu ermöglichen; beim Vater und dessen Umfeld sei dies nicht der Fall. Ein weiterer Verbleib der Kinder bei der Pflegefamilie C._ komme zufolge deren fehlender Eignung nicht in Frage, und eine Fremdplatzierung dürfte nur ultima ratio sein. Folglich sei die Obhut der Mutter zuzuteilen und diese intensiv sozialpädagogisch zu unterstützen.
3. Der Beschwerdeführer rügt zunächst - unter Verweis auf seine Vorbringen in der Berufung - eine mehrfache Verletzung des rechtlichen Gehörs sowie der Begründungspflicht.
Aus dem verfassungsmässigen Anspruch auf rechtliches Gehör folgt, dass die Behörde tatsächlich hört, prüft und in der Entscheidfindung berücksichtigt, was der Rechtssuchende ihr vorträgt (<ref-ruling> E. 2 S. 242 mit Hinweisen). Die daraus folgende behördliche Begründungspflicht erfordert jedoch nicht, dass sich die Behörde mit allen Parteistandpunkten einlässlich auseinandersetzt und jedes einzelne Vorbringen ausdrücklich widerlegt. Die Begründung muss so abgefasst sein, dass sich die betroffene Person über die Tragweite des Entscheids Rechenschaft geben und ihn in voller Kenntnis der Sache an die höhere Instanz weiterziehen kann. Die genannten Grundsätze gelten auch für eine Rechtsmittelinstanz (<ref-ruling> E. 3.3 S. 445; <ref-ruling> E. 4.3 S. 540; <ref-ruling> E. 3.2 S. 236; <ref-ruling> E. 2b S. 102 f., je mit Hinweisen). Der angefochtene Entscheid genügt den verfassungsrechtlichen Begründungsanforderungen. Der Beschwerdeführer war denn auch ohne weiteres in der Lage, das Urteil des Obergerichts in allen Teilen umfassend und sachgerecht anzufechten. Dies zeigen seine Rügen bzw. Ausführungen vor Bundesgericht.
4. Der Beschwerdeführer erhebt zwei Sachverhaltsrügen.
4.1 Zunächst kritisiert er die Schlüssigkeit des Gutachtens.
Wie jedes andere Beweismittel unterliegt das Gerichtsgutachten der freien Beweiswürdigung. Kriterien der Beweiswürdigung bilden die Vollständigkeit, die Nachvollziehbarkeit und die Schlüssigkeit des Gutachtens. Das Gericht hat zu prüfen, ob das Gutachten alle Fragen beantwortet, sich auf den zutreffenden Sachverhalt stützt und den Befund ausreichend begründet. Für die Sachverhaltsermittlung und Beweisabnahme bleibt das Gericht verantwortlich. Aus diesem Grund muss es die Schlussfolgerungen des Gutachtens derart nachvollziehen können, dass es zu beurteilen in der Lage ist, ob die gutachterlichen Folgerungen in sich geschlossen sind. Sofern die gutachterlichen Folgerungen weder als offensichtlich widersprüchlich erscheinen noch auf irrtümlichen tatsächlichen Feststellungen beruhen, muss sich das Gericht an die Auffassung des Gutachters halten. Es darf nur aus triftigen Gründen davon abweichen (<ref-ruling> E. 4.2.3 S. 391; <ref-ruling> E. 4.4.1 S. 269, je mit Hinweisen; <ref-ruling> E. 3.1 S. 547 f.; Urteil 5P.39/2004 vom 6. Oktober 2004 E. 6.1; Urteil 5A_636/2011 vom 10. Februar 2012 E. 4.3.1).
Der Beschwerdeführer führt aus, er habe den eingeholten Bericht bereits vor der Vorinstanz insofern kritisiert, als dieser lediglich auf Schilderungen Dritter beruhe, welche oft nur punktuell Kontakt mit einer Partei gehabt hätten und deshalb nur indirekt Wiedergegebenes wissen könnten; dies erwecke den Eindruck, dass die Berichterstatterin Partei für die Beschwerdegegnerin ergriffen habe und das Gericht kritiklos auf den einseitigen Bericht abgestellt habe.
Dabei übersieht der Beschwerdeführer einerseits, dass die erwähnten Drittpersonen mit den Kindern in Kontakt standen, um die es primär geht, sowie auch dass sich der Bericht zusätzlich auch auf die Akten stützt. Im Abstellen auf ein auf diesen Grundlagen beruhendes Gutachten kann keine Willkür erblickt werden.
Der Beschwerdeführer wirft der Vorinstanz ferner vor, kein kinderpsychiatrisches Gutachten eingeholt zu haben. Ob ein kinderpsychiatrisches Gutachten einzuholen ist, liegt im pflichtgemässen Ermessen des Gerichts (Urteil 5A_117/2007 vom 11. Oktober 2007 E. 6.2). Kann der massgebliche Sachverhalt auf andere Weise geklärt werden (dazu unten E. 4.2, 5. und 6.), so erweist sich der Verzicht auf die Anordnung eines solchen Gutachtens nicht als willkürlich (Urteil 5C.22/2005 vom 13. Mai 2005 E. 2.2 am Ende, publ. in: FamPra.ch 2005 S. 950; Urteil 5C.210/2000 vom 27. Oktober 2000, E. 2c, publ. in: FamPra.ch 2001 S. 606, je mit Hinweisen).
4.2 Sodann macht der Beschwerdeführer geltend, er habe in seiner Berufung darauf hingewiesen, dass bei A._ Verletzungen im Gesicht festgestellt worden seien, die gemäss Angaben von A._ von der Mutter zugefügt worden seien. Die Vorinstanz habe diesen Umstand ausser Acht gelassen.
Es trifft zu, dass die Vorinstanz zum fraglichen Vorfall nicht unmittelbar Stellung genommen hat. Indes thematisiert der Bericht der Familienberatung Olten-Gösgen die erwähnte Problematik, taxiert diese aber nicht als derart gravierend, dass sie einer Zusprechung der Obhut entgegenstünde; vielmehr habe das Fehlverhalten der Mutter auf einer bloss momentanen Überforderung beruht, während sie ihren Erziehungs- und Betreuungsaufgaben über all die Jahre hinweg zuverlässig nachgekommen und eine liebevolle Mutter gewesen sei. Indem das Obergericht dieser gutacherlichen Beurteilung folgte, ist es nicht in Willkür verfallen.
5. Der Beschwerdeführer rügt des Weiteren, die Vorinstanz habe <ref-law> (Untersuchungsgrundsatz) willkürlich angewendet.
Bei der Regelung von Belangen unmündiger Kinder gelten Untersuchungs- und Offizialmaxime ganz allgemein (<ref-law>). Die Untersuchungsmaxime verpflichtet den Richter, von sich aus alle Elemente in Betracht zu ziehen, die entscheidwesentlich sind, und unabhängig von den Anträgen der Parteien Beweise zu erheben. Diese Pflicht ist indes nicht ohne Grenzen und entbindet die Parteien nicht von einer aktiven Mitwirkung am Verfahren, indem sie Hinweise zum Sachverhalt machen oder Beweise bezeichnen (dazu BGE <ref-ruling>11 E. 3.21 und 3.2.2 S. 412 ff.). Den genannten Verfahrensgrundsätzen kommt zudem nicht etwa die Bedeutung zu, dass der Richter jedem Parteiantrag stattzugeben und von Amtes wegen sämtliche einschlägige Tatsachen festzustellen hätte. Die Untersuchungsmaxime schliesst eine vorweggenommene Beweiswürdigung nicht aus: Verfügt das Gericht über genügend Grundlagen für eine sachgerechte Entscheidung, kann es auf weitere Beweiserhebungen verzichten (<ref-ruling> E. 2.2.3 S. 735 mit Hinweisen). Wenn der massgebliche Sachverhalt sich auf andere Weise abklären lässt, verstösst auch der Verzicht auf ein bestimmtes Beweismittel nicht gegen Bundesrecht (dazu Urteil 5C.22/2005 vom 13. Mai 2005 E. 2.2, in: Fampra.ch 2005 S. 951 f.).
Wer sich auf den Untersuchungsgrundsatz beruft bzw. eine Verletzung desselben geltend macht, muss zunächst aufzeigen, dass das Gericht den Sachverhalt unvollständig und damit willkürlich festgestellt hat. Sodann muss der Beschwerdeführer diejenigen Tatsachen behaupten, die das Gericht festzustellen bzw. abzuklären unterlassen hat. Schliesslich obliegt es ihm darzutun, inwiefern die behaupteten Tatsachen für den Ausgang des Verfahrens entscheidend sind (zuletzt: Urteil 5A_299/2012 vom 21. Juni 2012 E. 3.4).
Den vorerwähnten Rügeanforderungen kommt der Beschwerdeführer vorliegend nicht nach. Im Übrigen weist nichts darauf hin, dass dem Obergericht die massgeblichen Sachverhaltselemente nicht zur Verfügung gestanden hätten (s. oben E. 4) und das Obergericht insofern der Willkür verfiel. Von einer Verletzung des Untersuchungsgrundsatzes kann folglich keine Rede sein.
6. Zudem rügt der Beschwerdeführer, die Vorinstanz habe <ref-law> willkürlich angewendet, indem sie die Kinder nicht angehört habe.
Gemäss <ref-law> sind Kinder anzuhören, sofern ihr Alter oder andere wichtige Gründe nicht dagegen sprechen. Im Sinne einer bundesgerichtlichen Richtlinie kommt die Anhörung ab dem vollendeten sechsten Altersjahr in Frage (Urteil 5A_397/2011 vom 14. Juli 2011 E. 2.3 mit Hinweisen, in: FamPra.ch 2011 S. 1031).
Die Vorinstanz hat von einer Anhörung abgesehen, weil einzig A._ das sechste Altersjahr nur knapp überschritten hatte, weil die Kinder sich bereits im Rahmen des Gesprächs mit der Familienberatung nicht zu sprechen trauten bzw. bedrückt gewirkt hätten und schliesslich auch weil dadurch eine Gleichbehandlung der Geschwister hergestellt werde.
Wenn es bereits einer spezialisierten Fachperson nicht gelingt, die Kinder anzuhören, so darf auch das Gericht auf eine Anhörung verzichten, denn Kinderanhörungen um der Anhörung willen sind zu vermeiden (<ref-ruling> E. 4 S. 554 f. mit Hinweisen). Insofern liegt keine willkürliche Anwendung von <ref-law> vor.
7. Nach dem Gesagten ist die Beschwerde abzuweisen, soweit darauf eingetreten werden kann.
7.1 Der Beschwerdeführer wird damit kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG). Wie die vorstehenden Erwägungen zeigen, muss die Beschwerde als von Anfang an aussichtslos bezeichnet werden, weshalb es an einer materiellen Voraussetzung der unentgeltlichen Rechtspflege fehlt (<ref-law>) und das entsprechende Gesuch des Beschwerdeführers abzuweisen ist.
Die Beschwerdegegnerin hat ein Gesuch um unentgeltliche Rechtspflege und Verbeiständung gestellt, dessen Voraussetzungen erfüllt sind. Ihr Gesuch ist indessen gegenstandslos geworden (<ref-ruling> E. 5 S. 11), soweit es die Befreiung von den Gerichtskosten betrifft, weil sie ohnehin keine Verfahrenskosten zu tragen hat. Dagegen ist es nicht gegenstandslos geworden, soweit es die Bestellung eines unentgeltlichen Rechtsbeistandes betrifft. Im Verfahren um aufschiebende Wirkung hat die Beschwerdegegnerin obsiegt. Entsprechend ist ihr eine Parteientschädigung zuzusprechen. Da begründete Zweifel an deren Einbringlichkeit bestehen, ist der unentgeltliche Rechtsbeistand für seine Bemühungen im Verfahren um aufschiebende Wirkung aus der Bundesgerichtskasse zu entschädigen (<ref-law>; <ref-ruling> E. 3d S. 326 f.).
Die Kostenbefreiung steht unter dem Vorbehalt, dass die Beschwerdegegnerin der Bundesgerichtskasse Ersatz zu leisten hat, wenn sie später dazu im Stande ist (<ref-law>).
7.2 Der Beschwerdeführer hat seine Beschwerde unter Vertretung einer Anwältin sowie unter Angabe einer Adresse in der Schweiz eingereicht. Seine Rechtsvertreterin hat ihr Mandat in der Folge niedergelegt und darauf hingewiesen, der Kontakt zum Beschwerdeführer sei abgebrochen (s. oben Sachverhalt C am Ende). Die Beschwerdegegnerin legte in ihrer Stellungnahme vom 9. Juli 2012 dar, der Beschwerdeführer halte sich mit den beiden Kindern in der Türkei auf; diesem Vorbringen hat der Beschwerdeführer jedenfalls nicht widersprochen. Somit ist der Aufenthalt des Beschwerdeführers unbekannt. Das Dispositiv des vorliegenden Urteils ist ihm demzufolge durch öffentliche Publikation im Bundesblatt mitzuteilen. Ein Exemplar des begründeten Urteils befindet sich zuhanden des Beschwerdeführers bei der Bundesgerichtskanzlei.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf eingetreten werden kann.
2. Das Gesuch um unentgeltliche Rechtspflege des Beschwerdeführers wird abgewiesen.
3. Die Gerichtskosten von Fr. 2'500.-- werden dem Beschwerdeführer auferlegt.
4. Dem Gesuch der Beschwerdegegnerin um unentgeltliche Rechtspflege wird für das Verfahren um aufschiebende Wirkung entsprochen, und ihr wird in der Person von Rechtsanwalt Guido Fischer, ein unentgeltlicher Rechtsbeistand bestellt.
5. Rechtsanwalt Guido Fischer wird für seine Bemühungen im bundesgerichtlichen Verfahren mit Fr. 500.-- aus der Bundesgerichtskasse entschädigt.
6. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Solothurn, Zivilkammer, schriftlich mitgeteilt.
Lausanne, 11. September 2012
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Hohl
Der Gerichtsschreiber: Schwander