Sachverhalt:
A. Am 5. November 2007 sprach das Amtsgericht Solothurn-Lebern X._ von den Vorwürfen der versuchten Nötigung und der sexuellen Nötigung zum Nachteil von A._ frei.
Gegen dieses Urteil erhob die Oberstaatsanwaltschaft des Kantons Solothurn Appellation an das Obergericht des Kantons Solothurn. Dieses erklärte X._ am 30. April 2009 der versuchten Nötigung und der sexuellen Nötigung zum Nachteil von A._ schuldig und verurteilte ihn zu einer Freiheitsstrafe von 13 Monaten, unter Gewährung des bedingten Vollzugs, mit einer Probezeit von zwei Jahren.
B. X._ führt Beschwerde in Strafsachen an das Bundesgericht. Er beantragt, das angefochtene Urteil sei aufzuheben, und er sei vom Vorwurf der versuchten Nötigung und der sexuellen Nötigung freizusprechen.
C. Es wurden keine Vernehmlassungen eingeholt.

Erwägungen:
1. Die Vorinstanz geht von folgendem Sachverhalt aus:
A._ begab sich am 7. Juli 2006 von Münster nach Solothurn. Nachdem sie den letzten Zug Richtung Münster verpasst hatte, traf sie mit dem Beschwerdeführer, den sie von früheren Begegnungen her kannte, zufällig zusammen und vereinbarte mit ihm, sich wie bisher an dessen Domizil in Solothurn zu prostituieren. Als Preis wurden Fr. 100.-- festgelegt.
Nachdem sich in der Wohnung beide ausgezogen und sich der Beschwerdeführer Fischerstiefel und Lederhandschuhe sowie A._ auf sein Geheiss Lederstiefel und lange Handschuhe angezogen hatten, kam es zwischen den beiden zu sexuellen Handlungen. Dabei brachte der Beschwerdeführer Wäscheklammern an den Brustwarzen der Geschädigten an und führte in deren After einen "Analplug" ein, den er mehrmals aufpumpte. Ferner kam es zu vaginalem und oralem Geschlechtsverkehr. Er drang ferner mit mehreren Fingern in ihren After ein und schlug ihr mit einem Rohrstock sowie einer Reitpeitsche auf das Gesäss. Er nannte sie dabei mehrmals seine Sklavin und gab ihr den Namen C8.
2. 2.1 Der Beschwerdeführer wendet sich gegen die Sachverhaltsfeststellung. Dabei rügt er zunächst, die Vorinstanz habe zu Unrecht angenommen, den Aussagen der Geschädigten komme aufgrund der Androhung von Sanktionen im Falle einer unwahren Aussage erhöhter Beweiswert zu. Diese Beweiswertzumessung sei unhaltbar und verletze den Grundsatz in dubio pro reo sowie das Willkürverbot (<ref-law>). Da keine Waffengleichheit geherrscht und die Vorinstanz seinen Aussagen schon im Voraus einen geringeren Beweiswert eingeräumt habe, sei auch das Rechtsgleichheitsgebot (<ref-law> und Art. 7 KV-SO) verletzt worden (Beschwerde, S. 14 f.).
2.2 Die Vorinstanz differenziert zwischen der Glaubwürdigkeit einer Person und der Glaubhaftigkeit ihrer Aussagen. Die Glaubwürdigkeit der Person ergebe sich aus ihrer prozessualen Stellung, namentlich aus den persönlichen Beziehungen und Bindungen zu den übrigen Prozessbeteiligten sowie aus der Gesamtwürdigung ihres Aussageverhaltens. Bei Würdigung von Zeugenaussagen, wie vorliegend bei A._, sei den Hinweisen auf die Straffolgen einer falschen Anschuldigung, der Irreführung der Rechtspflege sowie der Falschaussage Rechnung zu tragen. Unwahre Aussagen eines Beschuldigten hingegen würden strafrechtlich ohne Konsequenzen bleiben (angefochtenes Urteil, S. 14).
2.3 Als Beweiswürdigungsregel besagt der in <ref-law> und Art. 6 Ziff. 2 EMRK verankerte Grundsatz in dubio pro reo, dass sich der Strafrichter nicht von der Existenz eines für den Angeklagten ungünstigen Sachverhalts überzeugt erklären darf, wenn bei objektiver Betrachtung erhebliche und nicht zu unterdrückende Zweifel bestehen, ob sich der Sachverhalt so verwirklicht hat. Bloss abstrakte und theoretische Zweifel sind nicht massgebend, weil solche immer möglich sind und absolute Gewissheit nicht verlangt werden kann. Inwiefern dieser Grundsatz verletzt ist, prüft das Bundesgericht unter dem Gesichtspunkt der Willkür (<ref-ruling> E. 2a; Urteil des Bundesgerichts 6B_923/2008 vom 2. Februar 2009 E. 2).
2.4 Das Gleichbehandlungsgebot nach <ref-law> und das Willkürverbot nach <ref-law> sind eng miteinander verbunden. Ein Entscheid ist willkürlich, sofern er nicht auf ernsthaften sachlichen Gründen beruht oder wenn er sinn- und zwecklos ist. Er verletzt das Rechtsgleichheitsgebot, wenn er rechtliche Unterscheidungen trifft, für die ein vernünftiger Grund in den tatsächlichen Verhältnissen nicht ersichtlich ist, oder Unterscheidungen unterlässt, die sich aufgrund der Verhältnisse aufdrängen, wenn also Gleiches nicht nach Massgabe seiner Gleichheit gleich und Ungleiches nicht nach Massgabe seiner Ungleichheit ungleich behandelt wird. Vorausgesetzt ist, dass sich die ungerechtfertigte Gleich- bzw. Ungleichbehandlung auf eine wesentliche Tatsache bezieht. In dieser Hinsicht erscheint ein Verstoss gegen die Rechtsgleichheit als eine besondere Form der Willkür (vgl. <ref-ruling> E. 4.2 mit Hinweisen).
2.5 Die Einwände des Beschwerdeführers gegen die vorinstanzliche Beweiswürdigung sind nicht stichhaltig. Das Bundesgericht erwog in einem früheren, nicht publizierten Entscheid, dass Zeugenaussagen in der Regel bei der Beweiswürdigung ein grösseres Gewicht zukommen, weil bei dieser Gelegenheit erfolgte Falschaussagen der Strafandrohung von <ref-law> unterstehen (Urteil des Bundesgerichts 1P.22/1994 vom 3. Juni 1994 E. 2c). Die Vorinstanz stellt im Übrigen nicht ausschliesslich auf den höheren Beweiswert der Zeugenaussage von A._ ab, sondern nimmt eine Gesamtwürdigung ihres Aussageverhaltens vor. Zudem differenziert sie zwischen der Glaubwürdigkeit einer Person und der Glaubhaftigkeit ihrer Aussagen. Inwiefern die Vorinstanz hierbei gegen die Grundsätze in dubio pro reo, der Gleichbehandlung sowie des Willkürverbots verstossen haben sollte, ist nicht ersichtlich und wird vom Beschwerdeführer auch nicht näher dargelegt. Die Beschwerde erweist sich in diesem Punkt als unzulässig.
2.6 Der Beschwerdeführer legt im Weiteren ausführlich dar, inwiefern die Aussagen von A._ widersprüchlich und daher Zweifel an deren Glaubhaftigkeit angebracht seien.
Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat. Die Feststellung des Sachverhalts durch die Vorinstanz kann nur gerügt werden, wenn sie offensichtlich unrichtig, d.h. willkürlich im Sinne von <ref-law> ist (<ref-ruling> E. 1.2.2) oder wenn sie auf einer Verletzung von schweizerischem Recht im Sinne von <ref-law> beruht (<ref-law>). Die Rüge der offensichtlich unrichtigen Feststellung des Sachverhalts prüft das Bundesgericht gemäss <ref-law> nur insoweit, als in der Beschwerde explizit vorgebracht und substantiiert dargelegt wird, inwiefern der Entscheid an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 1.4.3; <ref-ruling> E. 1.3 mit Hinweisen).
2.7 Was der Beschwerdeführer gegen die tatsächlichen Feststellungen der Vorinstanz einwendet, erschöpft sich in einer blossen appellatorischen Kritik am angefochtenen Urteil, die für die Begründung einer willkürlichen Feststellung des Sachverhalts nicht genügt. Er beschränkt sich darauf, die eigene Sichtweise der Verhältnisse darzulegen, indem er verschiedene Aussagen von A._ vergleicht und angebliche Widersprüche aufzeigt, die Zweifel an ihrer Glaubwürdigkeit begründen sollen (Beschwerde, S. 10 ff.).
Diese Ausführungen des Beschwerdeführers sind nicht geeignet, offensichtlich erhebliche und schlechterdings nicht zu unterdrückende Zweifel daran darzutun, dass sich der Sachverhalt, wie von der Vorinstanz festgestellt, verwirklicht hat. Denn für die Begründung von Willkür genügt praxisgemäss nicht, dass das angefochtene Urteil mit der Darstellung des Beschwerdeführers nicht übereinstimmt oder eine andere Lösung oder Würdigung vertretbar erscheint oder gar vorzuziehen wäre (<ref-ruling> nicht publ. E. 4.1; <ref-ruling> E. 2b mit Hinweisen). Willkür im Sinne von <ref-law> liegt nach ständiger Rechtsprechung nur vor, wenn der angefochtene Entscheid auf einer schlechterdings unhaltbaren oder widersprüchlichen Beweiswürdigung beruht, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 5.4). Dies ist vorliegend nicht der Fall. Die Vorinstanz legt ausführlich dar, weshalb im Wesentlichen auf die Aussagen von A._ abzustellen ist. Die Beweiswürdigung ist denn auch nicht zu beanstanden. Auf die Beschwerde ist in diesem Punkt nicht einzutreten.
3. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens trägt der Beschwerdeführer die Kosten des Verfahrens (<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, 23. November 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Favre Keller