Sachverhalt:
A. Y._ und X._ sind die Eltern des Sohnes Z._, geb. 1999.
B. B.a Mit Urteil des Kantonsgerichts Appenzell Ausserrhoden vom 3. Juli 2006 wurde die Ehe der Parteien geschieden und es wurden die Nebenfolgen der Scheidung geregelt. Z._ wurde unter die elterliche Sorge und Obhut des Vaters gestellt, es wurde der persönliche Verkehr mit der Mutter geregelt sowie deren Kinderunterhaltsbeitrag festgelegt. Weiter wurde eine Erziehungsbeistandschaft für Z._ angeordnet.
B.b Y._ gelangte gegen dieses Urteil mit Appellation an das Obergericht des Kantons Appenzell Ausserrhoden. Sie beantragte insbesondere die Zuteilung der elterlichen Sorge. Betreffend den Scheidungspunkt, die güterrechtliche Auseinandersetzung sowie die Aufteilung der beruflichen Vorsorge blieb das Urteil unangefochten und ist somit in Rechtskraft erwachsen.
In Abweisung der Appellation beliess das Obergericht mit Urteil vom 23. März 2009 die elterliche Sorge beim Vater. Dessen elterliche Obhut wurde hingegen aufgehoben und die zwischenzeitlich vollzogene Fremdplatzierung von Z._ in einer Pflegefamilie bis zu seinem Abschluss der Oberstufe angeordnet. Beiden Elternteilen wurde abwechslungsweise ein Besuchsrecht von jedem zweiten Wochenende und überdies ein jährliches Ferienrecht von zwei Wochen gewährt. Im Übrigen wurde Y._ verpflichtet, ihre Kinderrenten der Invalidenversicherung und der Lebensversicherung an X._ weiterzuleiten und dieser wurde verpflichtet, monatlich Fr. 983.-- für die Pflegefamilie zu bezahlen.
C. X._ (fortan: Beschwerdeführer) ist am 18. September 2009 mit Beschwerde in Zivilsachen an das Bundesgericht gelangt. Er beantragt, es sei das Urteil des Obergerichts teilweise aufzuheben und es sei vom Entzug der elterlichen Obhut abzusehen sowie die obergerichtliche Besuchs- und Ferienrechtsregelung aufzuheben. Im Weiteren sei ihm die unentgeltliche Rechtspflege zu gewähren und Y._ (fortan: Beschwerdegegnerin) zu verpflichten, die vorinstanzlichen Kosten und eine angemessene Parteientschädigung zu bezahlen.
Es sind keine Antworten eingeholt worden.

Erwägungen:
1. 1.1 Angefochten ist ein obergerichtlicher Entscheid betreffend die Nebenfolgen der Ehescheidung. Dabei handelt es sich um einen letztinstanzlichen Entscheid in Zivilsachen (Art. 72 Abs. 1 und Art. 75 Abs. 1 BGG). Streitpunkt vor Bundesgericht ist die Regelung der Kinderbelange, so insbesondere die Zuteilung der elterlichen Obhut über den gemeinsamen Sohn Z._, weshalb eine nicht vermögensrechtliche Streitigkeit vorliegt. Die Beschwerde in Zivilsachen ist somit grundsätzlich zulässig.
1.2 Mit der Beschwerde kann insbesondere die Verletzung von Bundes- und Völkerrecht gerügt werden (Art. 95 lit. a und b BGG). Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinn von <ref-law> beruht und die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Nach <ref-law> ist in der Begründung in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt. Dabei ist es unerlässlich, dass die Beschwerde auf die Begründung des angefochtenen Entscheids eingeht und im Einzelnen aufzeigt, worin eine Verletzung von Bundesrecht liegt. Der Beschwerdeführer soll in der Beschwerdeschrift mit seiner Kritik an den als rechtsfehlerhaft erachteten Erwägungen der Vorinstanz ansetzen (vgl. <ref-ruling> E. 2a S. 400; Urteil 4A_22/2008 vom 10. April 2008 E. 1). Strengere Anforderungen gelten, wenn die Verletzung von Grundrechten, einschliesslich Willkür bei der Sachverhaltsfeststellung (<ref-ruling> E. 1.4.3 S. 255), geltend gemacht wird. Die Beschwerdeschrift muss die wesentlichen Tatsachen und eine kurz gefasste Darlegung darüber enthalten, welche verfassungsmässigen Rechte inwiefern durch den angefochtenen Entscheid verletzt worden sind. Das Bundesgericht prüft nur klar und detailliert erhobene und belegte Rügen; auf rein appellatorische Kritik am angefochtenen Entscheid tritt es nicht ein. Wird eine Verletzung des Willkürverbots geltend gemacht, muss anhand der angefochtenen Subsumtion im Einzelnen dargelegt werden, inwiefern der Entscheid an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 2.1 S. 246; <ref-ruling> E. 4.1 S. 588 f.).
2. Hauptstreitpunkt des vorliegenden Verfahrens bildet die Frage, ob Z._ unter die Obhut seines Vaters gestellt werden oder bei einer Pflegefamilie aufwachsen soll. In diesem Zusammenhang rügt der Beschwerdeführer eine Verletzung von <ref-law> und <ref-law>. Im Weiteren erachtet er verschiedene Sachverhaltsfeststellungen des Obergerichts als willkürlich.
3. 3.1 Vorab macht der Beschwerdeführer seitenlange Ausführungen zum Sachverhalt und zur Prozessgeschichte. Dabei schildert er seine Sicht der Dinge und versucht insbesondere die obergerichtlich angeführten Gründe für die Einholung eines zweiten Gutachtens betreffend die Obhutsfrage sowie dessen Inhalt zu erläutern. Nach Ansicht des Beschwerdeführers stützt sich der obergerichtliche Obhutszuteilungsentscheid zu stark auf dieses Gutachten ab. Zudem weise das Gutachten Ungenauigkeiten und Fehler auf. Es treffe beispielsweise nicht zu, dass er sich mit der Beschwerdegegnerin ständig im Streit befände, wie es aufgrund des Gutachtens und auch der Befragung der Kinderbeistände den Anschein mache. Vielmehr pflege er mit ihr seit Jahren keinen Kontakt mehr. Ohnehin habe sich die Situation grundlegend verändert. Das Gutachten, mit welchem die Fremdplatzierung empfohlen wurde, habe einerseits darauf beruht, dass Z._ bei der Pflegefamilie gut aufgehoben war, andererseits darauf, dass im Zeitpunkt der Erstellung des Gutachtens die Sorgerechtszuteilung noch umstritten war und deshalb angeblich von beiden Seiten Druck auf das Kind ausgeübt wurde. Die Zuteilung der elterlichen Sorge sei heute, sofern die Beschwerdegegnerin nicht auch eine Beschwerde einreiche, gerichtlich entschieden und es werde nur schon dadurch eine grosse Beruhigung eintreten. Zudem sei die Beschwerdegegnerin kürzlich in den Kanton Aargau umgezogen und Z._ sei ein aktives Mitglied des Fussballclubs und besuche einen Schwimmkurs. Auch sei darauf hinzuweisen, dass die Pflegemutter von Z._ im Frühling oder Frühsommer 2009 an Leukämie erkrankt sei und sich immer wieder in mehrwöchigen Therapien befinde.
3.2 Aus den Vorbringen des Beschwerdeführers geht nicht hervor, weshalb und inwiefern die Sachverhaltsfeststellungen des Obergerichts offensichtlich falsch und damit willkürlich sein sollten. Vielmehr begnügt er sich damit, seine Sichtweise des Verfahrensablaufs und der Geschehnisse zu schildern und in allgemeiner Weise Kritik am Sachverhalt des Obergerichts zu üben. Dabei versucht er, diesen beliebig zu ergänzen. Damit genügt er den Begründungsanforderungen für die Rüge der willkürlichen Sachverhaltsfeststellungen in keiner Weise. Insbesondere geht aus der Beschwerde nicht klar hervor, weshalb das Obergericht vorliegend nicht auf das zweite Gutachten hätte abstellen sollen. Dem Obergericht kann nicht der Vorwurf gemacht werden, es hätte die Feststellungen dieses Gutachtens unkritisch übernommen oder sich nicht genügend mit allen relevanten Umständen auseinander gesetzt bzw. diese nicht sorgfältig gegeneinander abgewogen. Was den Vorwurf an der obergerichtlichen Feststellung betrifft, wonach sich die Parteien ständig im Streit befänden, geht aus der Begründung ebenfalls nicht klar hervor, inwiefern der vom Beschwerdeführer behauptete Umstand, dass die Parteien seit Jahren keinen Kontakt mehr pflegen, am Ergebnis etwas geändert hätte. Immerhin ist sowohl dem obergerichtlichen Urteil wie auch den Ausführungen des Beschwerdeführers deutlich zu entnehmen, dass sich der Kontakt zwischen den Parteien nach wie vor äusserst schwierig gestaltet, was sich negativ auf die Situation von Z._ auswirkt und insbesondere den Vollzug des Besuchsrechts nicht vereinfacht. Der Beschwerdeführer betont wiederholt, wie grundlegend sich die Situation zwischenzeitlich verändert habe, ohne den Eintritt von relevanten Änderungen für die Obhutsfrage von Z._ aufzuzeigen. Entgegen seiner Behauptung beruht die gutachterliche Empfehlung der Fremdplatzierung nicht hauptsächlich darauf, dass die Sorgerechtszuteilung zu diesem Zeitpunkt umstritten war, weshalb von beiden Seiten Druck auf das Kind ausgeübt worden ist. Vielmehr nennt das Gutachten auch die eingeschränkte Erziehungsfähigkeit der Eltern, den Umstand, dass Z._ sich bei seinen erziehungserfahrenen Pflegeeltern sehr wohl fühlt und jeweils während dem Aufenthalt bei ihnen aufblüht sowie die fehlende Kooperationsbereitschaft der Eltern als wichtige Gründe, welche für die Fortführung der Betreuung in der Pflegefamilie sprechen. Inwiefern der Entscheid über die Zuteilung der elterlichen Sorge zu einer relevanten Änderung der Situation geführt haben sollte, ist nicht nachvollziehbar. Immerhin ist die Obhutsfrage nach wie vor strittig, weshalb davon auszugehen ist, dass der Druck, der gemäss Ausführungen des Gutachtens auf Z._ lastet, nach wie vor besteht. Der Beschwerdeführer betont wiederholt, dass die gutachterliche Empfehlung der Fremdplatzierung wie auch der obergerichtliche Obhutsentscheid vor dem Hintergrund der strittigen Sorgerechtszuteilung ergangen seien. Dieser Argumentation kann indes nicht gefolgt werden. Die Fragen, die mit dem Gutachten zu beantworten waren, betreffen insbesondere die Erziehungsfähigkeit der Eltern und zielen auf eine längerfristige Obhutslösung - und damit eindeutig auch auf die Zeit nach der Zuteilung der elterlichen Sorge - hin. Das Gutachten wie auch das angefochtene Urteil sprechen sich klar dafür aus, dass Z._ bis zum Ende seiner Schulzeit bei der Pflegefamilie bleiben soll. Dass die Fremdplatzierung nur als Übergangslösung für die Zeit der strittigen Sorgerechtszuteilung gedacht worden wäre, kann vor diesem Hintergrund nicht ernsthaft behauptet werden. Im Übrigen handelt es sich bei den Vorbringen betreffend die angebliche Erkrankung der Pflegemutter, den Wegzug der Beschwerdegegnerin in den Kanton Aargau und die Sportaktivitäten des Kindes teilweise um Tatsachen, die erst nach dem angefochtenen Urteil eingetreten sind. Damit sind sie vor Bundesgericht als echte tatsächliche Noven unzulässig. Soweit sie hingegen bereits früher eingetreten wären, könnten sie vor Bundesgericht nur dann beachtet werden, wenn erst der obergerichtliche Entscheid für diese neuen Vorbringen Anlass gegeben hätte. Dass dem so sei, macht der Beschwerdeführer jedoch nicht geltend, weshalb auf seine Vorbringen nicht einzutreten ist (<ref-law>; Urteil 5A_790/2008 vom 16. Januar 2009 E. 2.3). Das Gesagte gilt auch betreffend die Ausführungen des Beschwerdeführers zu seiner Betreuungsfähigkeit mit gelegentlicher Beanspruchung einer Tagesmutter oder des Mittagstischs sowie betreffend die gute Beziehung von Z._ zu dem drei Jahre älteren Cousin.
4. Der Beschwerdeführer rügt weiter <ref-law> als verletzt. Seiner Ansicht nach besteht vorliegend keine Gefährdung des Kindes, welche eine Fremdplatzierung rechtfertigen würde.
4.1 Dazu führt er insbesondere aus, das Gutachten sei von der falschen Annahme ausgegangen, wonach er die Erziehung von Z._ nicht voll übernehmen könne. Jedoch werde nirgends konkret und stichhaltig aufgeführt, warum er hiezu nicht in der Lage sein sollte. Zudem gehe das Obergericht fälschlicherweise weiter davon aus, Z._ stehe unter Druck, weil er sich entscheiden müsse, bei wem er leben möchte. Dieser Druck sei nun aber mit Zuteilung der elterlichen Sorge nicht mehr vorhanden.
4.2 Die behauptete Verletzung von <ref-law> wird weitgehend mit wiederholter Kritik am Sachverhalt begründet, so etwa hinsichtlich der Betreuungssituation beim Beschwerdeführer. Wie bereits ausgeführt handelt es sich hierbei um neue und damit unzulässige Vorbringen (E. 3.2). Ohnehin genügt die Begründung weder den Begründungsanforderungen für eine Sachverhaltsrüge noch zur Geltendmachung einer Verletzung von <ref-law>. Soweit der Beschwerdeführer vorbringt, das Obergericht habe nicht konkret und stichhaltig aufgeführt, weshalb seine Erziehungsfähigkeit ungenügend sein sollte, spricht er zudem die Begründungspflicht des Richters als Ausfluss des rechtlichen Gehörs an. Er unterlässt es jedoch, eine Verletzung von <ref-law> explizit zu rügen und führt auch nicht weiter aus, weshalb und inwiefern das Obergericht vorliegend der Begründungspflicht nicht nachgekommen sein sollte. Ohnehin trifft es nicht zu, dass das angefochtene Urteil keine genügenden Ausführungen zur Erziehungsfähigkeit enthält. Vielmehr setzt sich das Obergericht eingehend mit den diesbezüglichen Ausführungen des Gutachtens sowie der Befragungen der Beistände und der Pflegeeltern auseinander. Auf diese Begründungselemente geht der Beschwerdeführer indes nicht ein. Betreffend die wiederholte Behauptung der veränderten Situation ist es - wie bereits ausgeführt - weder ersichtlich noch in der Beschwerde nachvollziehbar dargelegt, weshalb sich die Obhutsfrage mit Zuteilung der elterlichen Sorge grundlegend verändert hätte (E. 2.2). Insgesamt bringt der Beschwerdeführer nichts vor, was eine Verletzung von <ref-law> erkennen liesse. Vielmehr ist festzuhalten, dass sich das Obergericht mit allen relevanten Obhutszuteilungskriterien eingehend auseinandergesetzt, diese geprüft und sorgfältig gegeneinander abgewogen hat. Schliesslich ist anzumerken, dass den kantonalen Behörden, welche die Verhältnisse und die Parteien besser kennen als das Bundesgericht, bei der Regelung der Obhut ein erhebliches Ermessen zusteht, weshalb das Bundesgericht eine gewisse Zurückhaltung in der Überprüfung solcher Urteile übt (vgl. Urteil 5P.507/2006 vom 5. April 2007 E. 4.2).
5. Schliesslich rügt der Beschwerdeführer eine Verletzung von <ref-law>, da Z._ vor Erlass des Fremdplatzierungsentscheids nicht angehört worden sei.
5.1 Gemäss <ref-law> ist das Kind vor dem Erlass von Kindesschutzmassnahmen in geeigneter Weise persönlich anzuhören, sofern nicht sein Alter oder wichtige Gründe dagegen sprechen. Was den Ausschlussgrund des Alters anbelangt, hat das Bundesgericht mit Bezug auf die Kinderzuteilung festgehalten, dass die Anhörung im Sinn einer Richtlinie ab dem vollendeten sechsten Altersjahr in Frage kommt, soweit diese als Beweismittel beantragt ist (<ref-ruling> E. 1.2.3 f. S. 557). Im erwähnten Entscheid hat das Bundesgericht auch auf die kinderpsychologische Literatur verwiesen, wonach formallogische Denkoperationen erst ab ungefähr elf bis dreizehn Jahren möglich sind und auch die sprachliche Differenzierungs- und Abstraktionsfähigkeit erst ab ungefähr diesem Alter entwickelt ist (<ref-ruling> E. 1.2.2 S. 556 f.). Indes kann einerseits die Kindesanhörung auch zwischen sechs und elf bis dreizehn Jahren ein wertvolles Element bei der Feststellung des in Kinderbelangen von Amtes wegen zu ermittelnden Sachverhaltes bilden und sind andererseits die genannten Alterslimiten nicht schematisch anzuwenden, sondern ist auf den jeweiligen Entwicklungsstand des Kindes abzustellen (Urteil 5C.149/2006 vom 10. Juli 2006 E. 1.2, in: FamPra.ch 2006 S. 978). Im vorliegenden Fall war Z._ im Zeitpunkt der obergerichtlichen Beurteilung 9 Jahre alt, wobei er als normal entwickelt beschrieben wird. Diese Feststellungen lassen darauf schliessen, dass Z._ fähig gewesen wäre, sich über die Tragweite der verfügten Massnahmen ein Bild zu machen bzw. über die nötigen kognitiven Fähigkeiten verfügt hätte, weshalb das Alter einer Anhörung grundsätzlich nicht entgegengestanden hätte. Indes ist zu beachten, dass die Parteien im kantonalen Verfahren keine Kindesbefragung beantragt haben und betreffend die Zuteilung der elterlichen Sorge und Obhut bereits zwei Gutachten erstellt worden sind. Bei der Erstellung dieser Gutachten wurden auch Gespräche mit Z._, insbesondere betreffend seine Wohnsituation und seine diesbezüglichen Neigungen, geführt. Dieser Umstand sowie die Gefahr, dass eine weitere Befragung Z._ zusätzlich in seinem Loyalitätskonflikt hätte belasten können, erachtet das Obergericht als Gründe, welche gegen eine gerichtliche Anhörung des Kindes im Appellationsverfahren sprachen.
5.2 Mit der obergerichtlichen Begründung zum Verzicht auf eine gerichtliche Anhörung setzt sich der Beschwerdeführer nicht ansatzweise auseinander. Stattdessen begnügt er sich mit der Behauptung, anlässlich der beiden Begutachtungen seien Z._ entscheidende, seine Wohnwünsche betreffende Fragen nicht gestellt worden. Jedoch wurde Z._ im kantonalen Verfahren bereits zweimal einlässlich begutachtet und dabei nach seinen Neigungen in der Obhutsfrage befragt. Das Obergericht hat sich bei seinem Entscheid auf diese Gutachten abgestützt und sich damit auseinander gesetzt. Vor diesem Hintergrund kann nicht gesagt werden, Z._ sei nicht bereits in genügender Weise in das Verfahren einbezogen worden oder habe seine Sicht der Verhältnisse nicht darlegen können, weshalb der vorliegende Verzicht auf eine gerichtliche Kindesbefragung keine Verletzung von <ref-law> darstellt. Anzumerken ist schliesslich, dass den kantonalen Behörden auch in diesem Bereich ein gewisses Ermessen zusteht (Urteil 5P.507/2006 vom 5. April 2007 E. 4.4).
6. Nach dem Gesagten ist der Beschwerde insgesamt kein Erfolg beschieden. Ausgangsgemäss trägt der Beschwerdeführer die Gerichtskosten (<ref-law>). Sein Gesuch um unentgeltliche Rechtspflege ist abzuweisen, da seine Anträge, soweit darauf überhaupt einzutreten war, von vornherein aussichtslos waren (<ref-law>). Da die Beschwerdegegnerin zudem nicht zur Vernehmlassung eingeladen worden ist, erübrigt sich ihr Gesuch um unentgeltliche Rechtspflege.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf eingetreten werden kann.
2. Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 1'500.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Parteien und dem Obergericht von Appenzell Ausserrhoden, 1. Abteilung, schriftlich mitgeteilt.
Lausanne, 25. November 2009
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Die Gerichtsschreiberin:
Hohl Gut Kägi