Sachverhalt:
A. Der Amtsgerichtsstatthalter von Olten-Gösgen sprach X._ mit Urteil vom 26. Januar 2007 der sexuellen Handlungen mit Kindern schuldig. Er verurteilte ihn zu einer bedingten Geldstrafe von 120 Tagessätzen zu Fr. 140.--. Gegen das Urteil erhob X._ Appellation. Das Obergericht des Kantons Solothurn bestätigte mit Urteil vom 16. Februar 2009 den Schuld- und Strafpunkt.
B. Mit Beschwerde in Strafsachen beantragt X._, das Urteil des Obergerichts sei aufzuheben, und er sei vom Vorwurf freizusprechen. Im Übrigen sei die Sache zu neuer Entscheidung im Zivil- und Kostenpunkt an die Vorinstanz zurückzuweisen.

Erwägungen:
1. Die Beschwerde richtet sich gegen die vorinstanzliche Beweiswürdigung.
1.1 Der Anklageschrift liegt folgender Sachverhalt zugrunde:
Im Sommer 2000 übernachtete die damals neunjährige Geschädigte A._ im Haus des Beschwerdeführers. Zu einer nicht näher bekannten Zeit nachts begab sich der Beschwerdeführer ins Kinderzimmer von Y._, seiner jüngsten Tochter. Der Beschwerdeführer beugte sich zur sich schlafend stellenden Geschädigten hinunter und griff ihr mit einer Hand unter die Pyjamahose. Er berührte und streichelte sie kurz im Genitalbereich. A._ liess sich nichts anmerken.
1.2 Die Vorinstanz erachtet den Vorwurf aufgrund der glaubhaften Aussagen der Geschädigten als erstellt (s. angefochtenes Urteil E. 9 S. 18). Anlässlich der Videoeinvernahme habe die Geschädigte ausgesagt, vor ungefähr drei Jahren im Sommer bei ihrer Freundin Y._ übernachtet zu haben. Y._ sei im Bett an der Wand gelegen und sie selber auf der Matratze daneben. Es sei schon relativ spät gewesen, als sie Schritte im Flur gehört habe. Sie habe sich schlafend gestellt, weil sie gedacht habe, es sei den Eltern von Y._ nicht recht, dass sie so spät noch wach sei. Die Tür sei aufgegangen und Licht sei ins Zimmer gefallen. Jemand habe sich zu ihr hinunter gebückt und ihr mit der Hand die Pyjamahose angehoben. Ein Finger habe sie zwischen den Beinen berührt und über die Haut gestrichen. Ihre Freundin sei erwacht und habe gefragt: "He Papi, was machsch Du?". Er habe irgendwas gesagt wie: "Jo, ich ha wellä s'Liecht abmache" und habe das Zimmer wieder verlassen. Sie sei sicher, dass es der Beschwerdeführer gewesen sei, weil Y._ ihn mit "Papi" angesprochen habe und sie seine Stimme gehört habe. Sie habe schnell die Augen geöffnet und ihn gesehen, er sei ein bisschen dick. Ihre Mutter habe sie erst ca. 2 1/2 Jahren nach dem Vorkommnis darüber informiert, weil es ihr peinlich gewesen sei (s. angefochtenes Urteil E. 4.1 S. 8 f.). Die Vorinstanz hält fest, die Mutter der Geschädigten habe diese Schilderungen bestätigt. Anlässlich der polizeilichen Befragung von B._ sei bekannt geworden, dass die Eltern der Geschädigten von einer befreundeten Familie eine ähnliche Geschichte erfahren hätten. Die Tochter dieser Familie, D._, habe im Rahmen einer polizeilichen Videobefragung ausgesagt, mit Y._ im Zimmer übernachtet zu haben. Sie sei erwacht, weil sie das Gefühl gehabt habe, dass ihr jemand das T-Shirt etwas anhebe, mit der Hand in die Unterhose fasse und ihr die Brust lecke. Sie habe sich nicht getraut die Augen zu öffnen, weil sie Angst gehabt habe, es könne wahr sein. Sie habe das Gefühl gehabt, es müsse fast echt sein. Y._ habe sich umgedreht und eine Männerstimme habe "guet Nacht" gesagt. Jetzt wo sie wisse, dass dies noch jemanden passiert sei, denke sie, es sei kein Traum gewesen. Die Vorinstanz hält fest, diese Wiedergabe des Vorfalls stimme mit den Angaben der Mutter, C._, überein (s. angefochtenes Urteil E. 4.2 und 4.3 S. 9 f.). Die Vorinstanz folgert, die Duplizität der geschilderten Ereignisse sei derart auffallend, dass der Glaubhaftigkeit der Aussagen von D._ Gewicht zuzumessen sei. Die Aussagen beider Mädchen würden sich durch eine bemerkenswerte Detailtreue auszeichnen. Der Glaubwürdigkeit der Geschädigten stehe nicht entgegen, dass sie mit der Erzählung der Geschichte fast drei Jahre zugewartet habe. Dass sie sich die Geschichte ausgedacht habe, weil sie vom Erlebnis von D._ erfahren habe, erscheine wenig wahrscheinlich. Die Beteiligten hätten übereinstimmend ausgesagt, die Geschädigte habe erst davon erfahren, als sie ihrer Mutter die eigene Geschichte erzählt habe (s. angefochtenes Urteil E. 4.4 S. 11).
2. Der Beschwerdeführer rügt eine willkürliche Beweiswürdigung. Das Glaubhaftigkeitsgutachten über die Aussagen der Geschädigten A._ sei fehlerhaft und genüge den bundesgerichtlichen Minimalstandards offensichtlich nicht. Die Vorinstanz verletze zudem den Grundsatz "in dubio pro reo" und seinen Anspruch auf rechtliches Gehör, indem sie ihn entlastende Beweismittel nicht würdige.
2.1 Bei der Abklärung des Wahrheitsgehaltes von Zeugenaussagen hat sich die so genannte Aussageanalyse weitgehend durchgesetzt. Nach dem empirischen Ausgangspunkt der Aussageanalyse erfordern wahre und falsche Schilderungen unterschiedliche geistige Leistungen. Überprüft wird dabei in erster Linie die Hypothese, ob die aussagende Person unter Berücksichtigung der Umstände, der intellektuellen Leistungsfähigkeit und der Motivlage eine solche Aussage auch ohne realen Erlebnishintergrund machen könnte. Methodisch wird die Prüfung in der Weise vorgenommen, dass das im Rahmen eines hypothesengeleiteten Vorgehens durch Inhaltsanalyse (aussageimmanente Qualitätsmerkmale, so genannte Realkennzeichen) und Bewertung der Entstehungsgeschichte der Aussage sowie des Aussageverhaltens insgesamt gewonnene Ergebnis auf Fehlerquellen überprüft und die persönliche Kompetenz der aussagenden Person analysiert werden. Bei der Glaubhaftigkeitsbegutachtung ist immer davon auszugehen, dass die Aussage auch nicht realitätsbegründet sein kann. Ergibt die Prüfung, dass diese Unwahrhypothese (Nullhypothese) mit den erhobenen Fakten nicht mehr in Übereinstimmung stehen kann, so wird sie verworfen. Es gilt dann die Alternativhypothese, dass die Aussage wahr sei (<ref-ruling> E. 4.3 S. 45 mit Hinweis; <ref-ruling> E. 5 S. 58 f. mit Hinweisen). Auf Grund gedächtnispsychologischer Voraussetzungen kommt der Erstaussage eine entscheidende Bedeutung zu. Die akribische Rekonstruktion der Entstehungsgeschichte einer Aussage, besonders der Umstände der Erstbekundung, der so genannten Geburtsstunde der Aussage, ist unabdingbarer Bestandteil der Motivanalyse. Deshalb ist ein bloss stichwortartiges oder zusammenfassendes Protokoll der Erstaussage ungenügend. Mit den methodischen Anforderungen soll sichergestellt werden, dass durch suggestive Befragungstechniken verursachte Verfälschungen der Erinnerung und damit der Aussagen kindlicher Zeugen vom Gutachter entdeckt werden können (BGE <ref-ruling> E. 6.1 S. 59 f. mit Hinweisen).
2.2 Die Vorinstanz hält fest, ihr Eindruck, der auf die Glaubhaftigkeit der Aussagen der beiden Mädchen schliessen lasse, stehe auch in Übereinstimmung mit den Ergebnissen des Glaubhaftigkeitsgutachtens betreffend die Geschädigte A._. Die Gutachter hätten im Rahmen der Untersuchungshypothesen bei ihr keine Hinweise auf Einschränkungen, realitätsgerechte Wahrnehmungen zu machen, gefunden. Sie seien zum Schluss gelangt, die Darstellungen würden sich durch eine ganze Reihe von Merkmalen auszeichnen, welche bei einer erfundenen Aussage eher nicht zu erwarten wären, was die Hypothese der Glaubhaftigkeit stütze. Die Schlussfolgerungen der Gutachter würden sich auf eine persönliche Befragung sowie auf sämtliche Protokolle der polizeilichen Einvernahmen stützen. Weil ihnen somit die Aussagen der Eltern der Geschädigten sowie der Bericht der Stellenleiterin der Opferhilfe vorgelegen seien, hätten sie die Wahrscheinlichkeit suggestiver Einflüsse einschätzen können. Die Einschätzung, dass sich alle sehr darum bemüht hätten, eine suggestive Einflussnahme auf die Geschädigte zu vermeiden, werde durch die erwähnten Aktenstücke gestützt. Den Gutachtern sei nicht vorzuwerfen, dass sie auf eine persönliche Anhörung von D._ verzichteten. Deren Glaubhaftigkeit sei nicht zu beurteilen gewesen und ihre Schilderungen seien nur als Stütze für die Schlussfolgerungen in Bezug auf die Geschädigte beigezogen worden. Das Gutachten habe sich mit dem Gespräch zwischen der Geschädigten und der Mutter auseinandergesetzt. Es entspreche dem Regelfall, dass eine detaillierte Befragung erst in der dokumentierten Videobefragung erfolgt sei. Insgesamt vermöge das Gutachten den von der bundesgerichtlichen Rechtsprechung geforderten Standards zu genügen. Es beruhe auf vollständigen Unterlagen, sei in sich schlüssig und nachvollziehbar. Die Gutachter seien bei der kriterienorientierten Aussageanalyse auf nichts gestossen, was gegen die Glaubhaftigkeit der Aussagen spreche. Im Übrigen seien keine Anhaltspunkte erkennbar, die ein Motiv für eine Falschbezichtigung erkennen liessen (s. angefochtenes Urteil E. 4.5 S. 12 ff.).
2.3 Der Beschwerdeführer rügt methodische und qualitative Mängel des Gutachtens. Er bringt im Wesentlichen vor, die Gutachter hätten nicht auf eine persönliche Anhörung von D._ verzichten dürfen, zumal sie deren Aussagen einen "hohen Stellenwert" zugemessen hätten. Weiter sei das Gutachten nicht von der Nullhypothese ausgegangen, sondern habe zuerst drei Varianten der Real- oder Erlebnishypothese formuliert. Dieses Vorgehen sei unzulässig, weil der strafrechtlich relevante Vorwurf nur auf einer Erlebnishypothese beruhen könne. Anschliessend bilde das Gutachten neun Alternativhypothesen und bezeichne die Nullhypothese als "(Alternativ-) Hypothese 10". Sämtliche Hypothesen würden den angeblichen Übergriff gegen D._, welcher nicht Verfahrensgegenstand bilde, miteinbeziehen. Dies sei zirkelschlüssig, weil die Nullhypothese von vornherein ausscheide, falls die Aussagen von D._ als sehr glaubhaft qualifiziert würden. Die Gutachter würden die Argumente, welche die Alternativhypothese verwerfen würden, lediglich aufzählen, aber nicht bewerten bzw. gewichten. Das Gutachten schliesse mit der pauschalen Bemerkung ab, dass sich die Alternativhypothesen als unwahrscheinlich erweisen würden, weshalb sich die "Hypothese 1a" als die überzeugendste Variante herausstelle. Auch die Kompetenzanalyse sei grob vernachlässigt worden. Bei der "Exploration" der Geschädigten sei der Gesprächsverlauf mit den Gutachtern ungenügend dokumentiert worden. Deshalb sei die Schlussfolgerung, es seien keine Einschränkungen für eine realitätsgerechte Wahrnehmung ersichtlich, nicht nachvollziehbar. Weiter würden die Gutachter fälschlicherweise Suggestion ausschliesslich auf eine direkte Einflussnahme durch Dritte hin untersuchen. Die Uraussage der Geschädigten gegenüber der Mutter sei nicht dokumentiert worden. Bereits anlässlich dieses Gesprächs habe die Geschädigte erfahren, dass es einen "ähnlichen Vorfall" mit D._ gegeben habe. Auch die Aussagen der Geschädigten gegenüber Frau E._ von der Opferhilfe seien nur durch eine Aktennotiz dokumentiert worden. Vor diesem Gespräch hätten zwischen Frau E._ und den Eltern telefonische Kontakte stattgefunden, die geeignet gewesen seien, Erwartungen und Vorstellungen von Frau E._ zu begründen. Bei der polizeilichen Einvernahme sei die Geschädigte nicht gefragt worden, was sie erlebt, sondern was sie den Eltern und Frau E._ erzählt habe. Bereits diese Fragestellung drücke eine klare Erwartungshaltung aus. Zudem hätten die hohe Zahl der Aussagen und der Aussageempfänger einen hochsuggestiven Rahmen gebildet. Schliesslich hätten die Gutachter die zwei Videokassetten und die vier DVD's nicht visioniert, sondern die Qualität der Befragungen gestützt auf die schriftlichen Unterlagen beurteilt. Weiter bringt der Beschwerdeführer vor, die Beweiswürdigung sei auch abgesehen vom Gutachten einseitig und im Ergebnis willkürlich. Den Akten sei nicht zu entnehmen, dass die Vorinstanz die Videos über die Befragungen visioniert habe. Die Aussagen seiner Tochter und seiner Ehefrau seien nicht in die Beweiswürdigung einbezogen worden. Die Mutter der Geschädigten habe dieser bereits anlässlich deren Uraussage vom angeblichen Übergriff auf D._ erzählt. Das hohe Suggestionspotential dieser Information sei von der Vorinstanz nicht gewürdigt worden.
2.4 Die Prüfung der Glaubhaftigkeit von Aussagen ist primär Sache der Gerichte. Auf Begutachtungen ist nur bei Vorliegen besonderer Umstände zurückzugreifen. Das Gericht würdigt das Gutachten grundsätzlich frei. Es darf in Fachfragen nicht ohne triftige Gründe vom Gutachten abweichen und muss Abweichungen begründen. Das Abstellen auf nicht schlüssige Gutachten kann gegen <ref-law> verstossen, wenn gewichtige, zuverlässig begründete Tatsachen oder Indizien die Überzeugungskraft des Gutachtens ernstlich erschüttern. Willkür liegt vor, wenn die Behörde in ihrem Entscheid von Tatsachen ausgeht, die mit der tatsächlichen Situation in klarem Widerspruch stehen, auf einem offenkundigen Fehler beruhen oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderlaufen. Dabei genügt es nicht, wenn das Urteil sich nur in der Begründung als unhaltbar erweist. Eine Aufhebung rechtfertigt sich erst, wenn es im Ergebnis verfassungswidrig ist. Gemäss dem in <ref-law> und in Art. 6 Ziff. 2 EMRK verankerten Grundsatz "in dubio pro reo" ist bis zum gesetzlichen Nachweis der Schuld zu vermuten, dass der wegen einer strafbaren Handlung Angeklagte unschuldig ist (BGE <ref-ruling> E. 4 S. 57 f. mit Hinweisen).
2.5 Vorab ist festzuhalten, dass sich der Beschwerdeführer teilweise nicht mit den vorinstanzlichen Erwägungen auseinandersetzt, sondern seine Ausführungen wiederholt, welche er in der Appellation vorgebracht hat. Soweit seine Rügen deshalb den Begründungsanforderungen nicht genügen, ist darauf nicht einzutreten (<ref-law>, <ref-ruling> E. 1.4.2 S. 254).
2.5 Vorab ist festzuhalten, dass sich der Beschwerdeführer teilweise nicht mit den vorinstanzlichen Erwägungen auseinandersetzt, sondern seine Ausführungen wiederholt, welche er in der Appellation vorgebracht hat. Soweit seine Rügen deshalb den Begründungsanforderungen nicht genügen, ist darauf nicht einzutreten (<ref-law>, <ref-ruling> E. 1.4.2 S. 254).
2.6 2.6.1 Im vorliegenden Fall ist zu beachten, dass das Gutachten des Kinder- und Jugendpsychiatrischen Diensts des Kantons Solothurn vom 23. Dezember 2005 nicht die einzige Beweisgrundlage bildet. Die Vorinstanz hat sich ausführlich mit den Aussagen mehrerer Zeugen und Auskunftspersonen auseinandergesetzt. Ihre Beurteilung der Glaubhaftigkeit der Aussagen der Geschädigten hat sie mit dem Resultat des Gutachtens verglichen.
2.6.2 Das Untersuchungsrichteramt hat einen Auftrag zur Begutachtung der Glaubwürdigkeit der Geschädigten aufgrund von Divergenzen zwischen deren Aussagen und jenen des Beschwerdeführers erteilt (s. kantonale Akten, AS 172). Der Beschwerdeführer hat es unterlassen, anlässlich seiner Stellungnahme zum Fragekatalog an die Gutachter eine Begutachtung der Auskunftsperson D._ zu verlangen (s. kantonale Akten, AS 185). Auch nach Abschluss der Strafuntersuchung sowie im Rahmen des Appellationsverfahrens hat er keinen Beweisantrag auf Begutachtung von D._ gestellt (s. kantonale Akten, AS 213 und Schreiben des Beschwerdeführers vom 3. September 2007). Seine Rüge der fehlenden Begutachtung von D._ stellt deshalb ein neues Vorbringen rechtlicher Art dar, welches - im Gegensatz zu neuen tatsächlichen Vorbringen (vgl. <ref-law>) - grundsätzlich neu vorgetragen werden kann. Dieser Grundsatz wird jedoch eingeschränkt, wenn der Einwand der Sache nach das Beweisrecht betrifft und der Beschwerdeführer nach Treu und Glauben verpflichtet war, den Einwand bereits im kantonalen Verfahren zu erheben (<ref-ruling> E. 1 f S. 288; Urteil 6B_256/2008 vom 27. November 2008 E. 1.3). Im vorliegenden Fall erfolgte die Rüge des Beschwerdeführers in diesem Sinne verspätet, weshalb nicht darauf einzutreten ist. Im Übrigen sind die Aussagen von kindlichen Zeugen durch das Gericht selbst zu würdigen, sofern sie klar und verständlich sind und auch ohne besondere kinderpsychologische Fachkenntnisse interpretiert werden können (vgl. <ref-ruling> E. 2 S. 84 sowie E. 2.4 hiervor). Es sind keine besonderen Umstände ersichtlich, welche die Begutachtung von D._ verlangt hätten.
2.6.3 Dass die Vorinstanz die Videos der Befragungen nicht visioniert haben soll, erschöpft sich in einer unbelegten Behauptung des Beschwerdeführers. Betreffend das Gutachten erweist sich die Rüge als unbegründet. Die Gutachter halten die Geschädigte als fähig, realitätsgerechte Wahrnehmungen zu machen und wiederzugeben. Für diese Beurteilung stützen sie sich auf das durchgeführte Explorationsgespräch sowie auf die Protokolle der Videoeinvernahmen (s. kantonale Akten, AS 229).
2.6.4 Das Gutachten hat im Rahmen der kriterienorientierten Aussageanalyse drei Real- oder Erlebnishypothesen aufgestellt: Die Übergriffe der Geschädigten und von D._ sind real erfolgt (Hypothese 1a) oder nur eine der beiden berichtet einen real erlebten Übergriff (Hypothese 1b oder 1c). Die Hypothese, dass es sich bei den geschilderten Episoden als reine Phantasieprodukte handelt (somit die Nullhypothese), wurde als "Alternativhypothese 10" bezeichnet. Die Gutachter haben für jede Alternativhypothese einzeln begründet, wieso sie sich als unwahrscheinlich herausstellt und haben gestützt darauf auch die Hypothesen 1b und 1c verworfen (vgl. kantonale Akten AS 240 ff.). Der Beschwerdeführer bemängelt zwar zu Recht, dass das Gutachten nicht mit der Nullhypothese beginnt. Entscheidend ist jedoch, dass das Vorgehen der Gutachter klar und nachvollziehbar ist. Zudem ist nicht ersichtlich, weshalb die Gutachter die Aussagen von D._ nicht als Hilfsttatsache hätten beiziehen dürfen.
2.6.5 Weiter haben die Gutachter die Aussagegeschichte rekonstruriert. Sie beurteilten eine suggestive Einflussnahme nicht nur aufgrund der Befragungstechnik (vgl. kantonale Akten AS 230), sondern haben insbesondere eine theoretische Suggestion durch die Eltern, die Opferhilfe-Beraterin oder durch weitere Dritte in der Zeitphase zwischen der Uraussage und der Erstbefragung bei der Polizei geprüft. In diesem Zusammenhang haben sie auch beachtet, dass die Uraussage erst anlässlich der polizeilichen Einvernahme dokumentiert worden ist (vgl. kantonale Akten AS 239 f.). Die Vorinstanz hat bei ihrer Beweiswürdigung die Möglichkeit einer Suggestion nicht nur gestützt auf das Gutachten, sondern auch aufgrund der weiteren Aktenlage verneint.
2.6.6 Schliesslich hat die Vorinstanz die Aussagen der Tochter und der Ehefrau des Beschwerdeführers in die Beweiswürdigung einbezogen. So führt sie aus, es ändere nichts an der Glaubwürdigkeit der Geschädigten, dass weder seine Frau noch seine Tochter etwas in dieser Hinsicht bemerkt hätten (vgl. angefochtenes Urteil E. 5.1 S. 15).
2.7 Zusammenfassend ist festzuhalten, dass die Vorinstanz das schlüssige Gutachten in ihre Beweiswürdigung einbeziehen durfte. Sie hat willkürfrei geschlossen, dass keine erheblichen und nicht zu unterdrückende Zweifel bestehen, dass sich der Sachverhalt wie angeklagt verwirklicht hat. Die Vorinstanz hat auch den Beschwerdeführer entlastende Beweismittel gewürdigt und somit seinen Anspruch auf rechtliches Gehör gewahrt. Das angefochtene Urteil, welches weder in der Begründung noch im Ergebnis offensichtlich unhaltbar ist, verstösst nicht gegen den Grundsatz "in dubio pro reo". Sämtliche Rügen des Beschwerdeführers erweisen sich als unbegründet.
3. Somit ist die Beschwerde abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Solothurn, Strafkammer, schriftlich mitgeteilt.
Lausanne, 3. September 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied : Die Gerichtsschreiberin:
Schneider Binz