Sachverhalt:
A. Am 23. Oktober 2008 erklärte das Kreisgericht VIII Bern-Laupen X._ der Vergewaltigung und der sexuellen Nötigung zum Nachteil von A._ schuldig und verurteilte ihn zu einer Freiheitsstrafe von 22 Monaten, bedingt aufgeschoben bei einer Probezeit von 2 Jahren. Weiter wurde er zur Bezahlung der Verfahrenskosten und der Genugtuungs- sowie Parteikosten von A._ verurteilt. Von der Anschuldigung des Führens eines Motorfahrzeugs in angetrunkenem Zustand sprach das Kreisgericht X._ frei.
B. Gegen dieses Urteil erhob der Generalprokurator, beschränkt auf die rechtliche Qualifikation der Schuldsprüche sowie auf die Sanktion, Appellation ans Obergericht des Kantons Bern. X._ schloss sich der Appellation, beschränkt auf den Schuldspruch der Vergewaltigung, an. Damit erwuchs das Urteil des Kreisgerichts VIII Bern-Laupen bezüglich des Freispruchs von der Anschuldigung des Führens eines Motorfahrzeugs in angetrunkenem Zustand sowie der Genugtuungszahlung in Rechtskraft.
Das Obergericht verurteilte X._ am 15. April 2009 wegen qualifizierter Vergewaltigung und qualifizierter sexueller Nötigung zu einer Freiheitsstrafe von 3 Jahren unter Gewährung des teilbedingten Strafvollzugs. Die Strafe wurde im Umfang von 12 Monaten unbedingt und im Umfang von 24 Monaten bedingt ausgesprochen bei einer Probezeit von 2 Jahren. Weiter verurteilte das Obergericht X._ zur Bezahlung der Verfahrens- und Parteikosten von A._.
C. X._ führt Beschwerde beim Bundesgericht. Er beantragt, der angefochtene Entscheid sei insoweit aufzuheben, als er der qualifizierten Vergewaltigung und der qualifizierten sexuellen Nötigung schuldig gesprochen wurde. Er sei der einfachen sexuellen Nötigung schuldig zu erklären und zu einer bedingten Freiheitsstrafe zu verurteilen. Eventualiter sei die Sache zur Festsetzung der Strafe an das Obergericht des Kantons Bern zurückzuweisen.
D. Es wurden keine Vernehmlassungen eingeholt.

Erwägungen:
1. Die Vorinstanz geht von folgendem Sachverhalt aus:
Am 5. Mai 2007, morgens um ca. 06.00 Uhr, empfing die Beschwerdegegnerin 1 in ihrem Salon den Beschwerdeführer und bot ihm Liebesdienste während fünf Stunden zum Preis von Fr. 1'000.-- an. Der Beschwerdeführer war damit nicht einverstanden und bot Fr. 700.--. Daraufhin zog er plötzlich ein Messer und zwang die Beschwerdegegnerin 1 zu sexuellen Handlungen mit ihm. Dabei kam es während rund einer Stunde zu vaginalem Geschlechtsverkehr mit Kondom von vorne und zu weiteren sexuellen Übergriffen (orale Penetrationen mit und ohne Kondom, manuelle Penetrationen vaginal und rektal). Ausserdem leckte der Beschwerdeführer die Beschwerdegegnerin 1 an den Brüsten und im Genitalbereich. Während der Tathandlungen war der Beschwerdeführer im Bereich von 2-3 o/oo alkoholisiert und hatte in der Nacht zuvor mutmasslich Kokain konsumiert.
2. 2.1 Der Beschwerdeführer rügt eine unrichtige Feststellung des Sachverhalts durch die Vorinstanz. Sie habe den in <ref-law> und Art. 6 Ziff. 2 EMRK verankerten Grundsatz "in dubio pro reo" verletzt, weil sie von einem für ihn ungünstigen Sachverhalt ausgegangen sei, obwohl sie diesbezüglich erhebliche und nicht zu unterdrückende Zweifel hätte haben müssen (Beschwerde, S. 3).
Konkret wendet sich der Beschwerdeführer gegen die Auffassung der Vorinstanz, es sei zu vaginalem Geschlechtsverkehr gekommen. Die Beschwerdegegnerin 1 habe diesen erst anlässlich der erstinstanzlichen Hauptverhandlung und nicht bereits anlässlich der mehrstündigen Einvernahmen durch Polizei und Untersuchungsrichter erwähnt. Zudem habe sie zwei verschiedene Erklärungen abgegeben, weshalb sie diese Aussage nicht früher gemacht habe. Sodann sei er aufgrund seines Blutalkoholgehalts gar nicht mehr in der Lage gewesen, zumal er kein steifes Glied hatte, in die Beschwerdegegnerin 1 einzudringen. Die Übersetzungsschwierigkeiten bei der erstinstanzlichen Befragung hätten schliesslich mehr Vorsicht erfordert, die Aussagen der Beschwerdegegnerin 1 zu seinen Ungunsten zu würdigen (Beschwerde, S. 4 f.).
2.2 Die Vorinstanz führt aus, dass es bei einem sexuellen Übergriff von über einer Stunde verständlich sei, die einzelnen Handlungen des Beschwerdeführers nicht in korrekter zeitlicher Abfolge schildern zu können. Erwähnt würden namentlich diejenigen Handlungen, die besonders traumatisch oder einschneidend erlebt worden seien. Dies treffe für "Thaileute" bei Oralsex zu. Die Aussagen der Beschwerdegegnerin 1 seien detailliert und stimmig und enthielten auch Aussergewöhnliches sowie Nebensächliches. So etwa, dass sie dem Beschwerdeführer die Finger habe lecken müssen und er stark geschwitzt habe. Zudem belaste sie sich durch ihre Aussagen teilweise auch selber. Dass sie den vaginalen Geschlechtsverkehr erst im Rahmen der erstinstanzlichen Hauptverhandlung erwähnt habe, ändere an ihrer Glaubwürdigkeit nichts (angefochtenes Urteil, S. 19 f.).
2.3 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (105 Abs. 1 BGG). Diese Sachverhaltsfeststellung 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>). Eine solche Rüge 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).
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 Die Ausführungen des Beschwerdeführers sind nicht geeignet, offensichtlich erhebliche und schlechterdings nicht zu unterdrückende Zweifel daran darzutun, dass sich der Anklagesachverhalt, wie von der Vorinstanz dargestellt, 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). Dass die Beschwerdegegnerin 1 erst anlässlich der erstinstanzlichen Hauptverhandlung und nicht bereits während der Einvernahmen von Polizei und Untersuchungsrichter oder gegenüber dem Zeugen Z._ den vaginalen Geschlechtsverkehr erwähnt und für ihr Schweigen zwei verschiedene Erklärungen abgegeben hat, könnte allenfalls gegen ihre Glaubwürdigkeit sprechen. Die Vorinstanz legt jedoch willkürfrei dar, weshalb sie dennoch auf die Aussagen der Beschwerdegegnerin 1 abstellt (angefochtenes Urteil, S. 19 ff.).
2.5 Inwiefern der Beschwerdeführer etwas aus den angeblichen Übersetzungsschwierigkeiten bei der erstinstanzlichen Befragung zu seinen Gunsten ableiten könnte, legt er nicht dar und ist auch nicht ersichtlich. Dasselbe gilt für die Behauptung, dass der Beschwerdeführer infolge Alkoholisierung kein steifes Glied hatte. Zwar sagte auch die Beschwerdegegnerin 1 aus, das Glied sei nicht steif gewesen, erwähnte aber, er habe "sexuell noch mit ihr machen" können (pag. 336). Deshalb kann nicht der Schluss gezogen werden, dass er nicht in der Lage war, in die Beschwerdegegnerin 1 einzudringen.
2.6 Die Vorinstanz konnte, ohne in Willkür zu verfallen, die Aussagen der Beschwerdegegnerin 1 als glaubhaft einstufen. Sie bediente sich den gängigen aussagepsychologischen Kriterien zur Beurteilung der Glaubwürdigkeit der Aussagen. Sie erachtete die Beschwerdegegnerin 1 namentlich deshalb als glaubwürdig, weil diese detailliert Interaktionen, Gespräche und Empfindungen schilderte und dabei auch Aussergewöhnliches und Nebensächliches erwähnte.
3. 3.1 Der Beschwerdeführer rügt die Verletzung des Grundsatzes "in dubio pro reo", indem die Vorinstanz im Rahmen der Beweiswürdigung angenommen habe, dass die Klinge des Messers so gross wie der Zeigefinger der Beschwerdegegnerin 1 gewesen sei (Beschwerde, S. 5 f.). Ferner gehe die Vorinstanz von den objektiv nicht belegbaren Schilderungen der Beschwerdegegnerin 1 aus und unterstelle ihm, es sei mit dem Messer zu gefährlichen Situationen in der Hals- und Kopfgegend gekommen (Beschwerde, S. 7). Schliesslich sei beweismässig nicht erstellt, dass er das Messer während der ganzen Zeit in den Händen gehalten habe (Beschwerde, S. 6).
3.2 Die Vorinstanz führt aus, dass die Beschwerdegegnerin 1 das Messer recht genau als Klappmesser, mit dem Flaschen geöffnet werden könnten, und als Schweizer Messer bzw. Armeemesser beschrieben habe. Die Vergleichsgrösse mit dem Zeigefinger stelle eine originelle und nachvollziehbare Schilderung dar. Die Beschwerdegegnerin 1 habe verschiedene Modelle von Schweizer Sackmessern verglichen, wobei sich ihre Beschreibung der mit den Merkmalen eines Sackmessers mittlerer Grösse deckten (angefochtenes Urteil, S. 20).
Bezüglich Messereinsatz habe die Beschwerdegegnerin 1 erlebnisbasierte Aussagen gemacht und diese konstant und nachvollziehbar vorgetragen (angefochtenes Urteil, S. 20, mit Hinweis auf pag. 43-45 der Vorakten). Sie schildere zudem glaubhaft, wie es dem Beschwerdeführer gelungen sei, mit dem Messer in der Hand Gleitmittel einzureiben und die übrigen Handlungen zu bewerkstelligen.
3.3 Auch in diesem Punkt ist nicht erkennbar, inwiefern die Vorinstanz eine willkürliche Tatbestandsfeststellung vorgenommen und gegen den Grundsatz in dubio pro reo verstossen haben sollte. In der vorinstanzlichen Hauptverhandlung wurde der Beschwerdegegnerin 1 ein Taschenmesser mittlerer Grösse vorgelegt und von ihr (abgesehen von der Farbe) als dem Tatmesser entsprechend bezeichnet. Sie schilderte gemäss Vorinstanz den Messereinsatz zudem detailliert, konstant und nachvollziehbar. Der Beschwerdeführer bringt keine Argumente vor, welche die vorinstanzliche Beweiswürdigung als willkürlich erscheinen und die Anwendung des Grundsatzes in dubio pro reo gebieten liesse. Die Beschwerde ist in diesem Punkt unbegründet.
4. 4.1 Der Beschwerdeführer rügt, die Vorinstanz habe den Begriff des gefährlichen Gegenstandes im Sinne von Art. 189 Abs. 3 und <ref-law> bundesrechtswidrig ausgelegt. Beim gefährlichen Gegenstand komme es auf seine Beschaffenheit und die Verwendung im Einzelfall an. Selbst wenn man annehme, er habe das Messer in der Hand gehalten, so habe zu keinem Zeitpunkt die konkrete Gefahr bzw. das geforderte Risiko von schweren oder gar tödlichen Verletzungen bestanden. Die Annahme, das Messer sei - unabsichtlich - in gefährliche Nähe des Kopfes der Beschwerdegegnerin 1 gekommen, sei beweismässig nicht erhärtet. Mit der Formulierung "unabsichtlich" gehe die Vorinstanz davon aus, dass weder ein Verletzungs- noch ein Tötungsvorsatz, auch nicht in Form des Eventualvorsatzes, bestanden habe. Die Qualifikationstatbestände der sexuellen Nötigung und Vergewaltigung seien deshalb nicht gegeben (Beschwerde, S. 7 f.).
4.2 Die Vorinstanz hält fest, dass der Beschwerdeführer rund eine Stunde lang unter Verwendung eines Taschenmessers mittlerer Grösse die Beschwerdegegnerin 1 sexuell missbraucht und ihr wiederholt gedroht habe, das Messer einzusetzen, sollte sie sich seinen Anordnungen nicht fügen. Hierbei habe er ihr das Messer teilweise an den Hals gehalten. Es sei nicht zu vermeiden gewesen, dass er während des Geschehens - teilweise auch unabsichtlich - in gefährliche Nähe ihres Halses und Kopfes gekommen sei. Die Beschwerdegegnerin 1 habe um ihr Leben gefürchtet. Die Vorinstanz führt weiter aus, es sei gerichtsnotorisch, dass am Hals bereits kleine Schnittwunden zu starken Blutungen und zum Tod eines Menschen führen könnten. Eine Waffe oder ein Gegenstand seien im Sinn des Gesetzes gefährlich, wenn sie sich objektiv eigneten, eine schwere Gesundheitsschädigung herbeizuführen, wobei es insbesondere auf die Art der Verwendung im Einzelfall ankomme. Im vorliegenden Fall sei die qualifizierte Begehungsform der Vergewaltigung und sexuellen Nötigung erfüllt (angefochtenes Urteil, S. 27).
4.3 Gemäss <ref-law> begeht eine sexuelle Nötigung, wer eine Person zur Duldung einer beischlafsähnlichen oder einer anderen sexuellen Handlung nötigt, namentlich indem er sie bedroht, Gewalt anwendet, sie unter psychischen Druck setzt oder zum Widerstand unfähig macht. Eine Vergewaltigung gemäss <ref-law> begeht, wer eine Person weiblichen Geschlechts zur Duldung des Beischlafs nötigt, namentlich indem er sie bedroht, Gewalt anwendet, sie unter psychischen Druck setzt oder zum Widerstand unfähig macht. Die qualifizierten Begehungsformen der sexuellen Nötigung (<ref-law>) und der Vergewaltigung (<ref-law>) sind erfüllt, wenn der Täter grausam handelt, namentlich wenn er eine gefährliche Waffe oder einen anderen gefährlichen Gegenstand verwendet.
4.4 Der qualifizierte Tatbestand ist nach der bundesgerichtlichen Rechtsprechung erfüllt, wenn der Täter unverhältnismässige oder gefährliche Tatmittel einsetzt und dadurch besondere Leiden zufügt, d.h. andere Leiden als diejenigen, welche die Frau schon deswegen erdulden muss, weil sie sexuell genötigt oder vergewaltigt wird. Dies sind Leiden, die mit der Begehung nicht notwendigerweise verknüpft sind, sondern die durch Sadismus oder zumindest durch die Absicht, Schmerzen zuzufügen, oder durch Rücksichtslosigkeit (Rohheit) und gegen fremde Leiden unbarmherzige Gesinnung (Gefühllosigkeit) bestimmt sind (<ref-ruling> E. 3d; Urteil 6P.153/2004 vom 10. Juni 2005 E. 6).
4.5 Die Ausführungen der Vorinstanz sind nicht zu beanstanden. Nach ihren verbindlichen Sachverhaltsfeststellungen hat der Beschwerdeführer die Beschwerdegegnerin 1 zwar nicht physisch verletzt, jedoch fortwährend mit seinem Taschenmesser bedroht, so dass sie um ihr Leben fürchten musste. Inwiefern der Beschwerdeführer einen Verletzungs- oder Tötungsvorsatz hatte, spielt entgegen seiner Ansicht keine Rolle. Zur Bejahung des qualifizierten Tatbestandes genügt die Verwendung des gefährlichen Gegenstandes zur Bedrohung des Opfers (Philipp Maier, Basler Kommentar StGB II, 2. Aufl. 2007, Art. 189 N. 47; Stefan Trechsel/Carlo Bertossa, Schweizerisches Strafgesetzbuch Praxiskommentar, 2008, Art. 189 N. 15 je mit Hinweisen). Massgebend ist, dass durch die Verwendung des gefährlichen Gegenstandes (oder wie vorliegend der gefährlichen Waffe) ein konkretes und nahes Risiko einer Tötung oder einer schweren Körperverletzung geschaffen wird. In Kombination mit der fortdauernden Bedrohung der Beschwerdegegnerin 1 und deren Todesangst ist die geforderte Intensität für die qualifizierte Begehungsform der Vergewaltigung und sexuellen Nötigung erfüllt. Die Beschwerde ist in diesem Punkt unbegründet.
5. 5.1 Der Beschwerdeführer macht schliesslich eine Verletzung des rechtlichen Gehörs geltend, indem die Vorinstanz sich mit seinen Einwänden nicht beschäftigt und ihr Urteil ungenügend begründet habe. Sie habe sich nicht damit auseinandergesetzt, dass die Beschwerdegegnerin 1 auf die Frage, ob es zu Geschlechtsverkehr gekommen sei, lediglich geantwortet habe, er habe Oralsex gemacht. Der vaginale Geschlechtsverkehr sei zwar gemäss Vorinstanz im Gewerbe der Beschwerdegegnerin 1 nichts Besonderes. Dies treffe jedoch für einen mit Gewalt erzwungenen Geschlechtsverkehr nicht zu. Ferner habe die Beschwerdegegnerin 1 gegenüber ihrer Vertrauensperson, dem Zeugen Z._, nichts von vaginalem Geschlechtsverkehr erzählt, was die Vorinstanz ebenso übergehe wie die entlastende Tatsache, dass die gynäkologische Untersuchung keine Hinweise auf erzwungenen Geschlechtsverkehr ergeben habe (Beschwerde, S. 4).
5.2 Dass sich die Vorinstanz nicht mit allen Argumenten des Beschwerdeführers auseinandersetzt, stellt keine Verletzung des rechtlichen Gehör gemäss <ref-law> dar. Der Betroffene hat das Recht, sich vor Erlass eines in seine Rechtsstellung eingreifenden Entscheids zur Sache zu äussern. Wesentlicher Bestandteil des Anspruchs auf rechtliches Gehör ist die Begründungspflicht. Die Begründung soll verhindern, dass sich die Behörde von unsachlichen Motiven leiten lässt, und dem Betroffenen erlaubt, die Verfügung gegebenenfalls sachgerecht anzufechten. Dies ist nur möglich, wenn sowohl er wie auch die Rechtsmittelinstanz sich über die Tragweite des Entscheids ein Bild machen können. In diesem Sinn müssen wenigstens kurz die Überlegungen genannt werden, von denen sich die Behörde hat leiten lassen und auf welche sich ihr Entscheid stützt. Dies bedeutet indessen nicht, dass sie sich ausdrücklich mit jeder tatbeständlichen Behauptung und jedem rechtlichen Einwand auseinandersetzen muss. Vielmehr kann sie sich auf die für den Entscheid wesentlichen Gesichtspunkte beschränken (<ref-ruling> E. 3.1 mit Hinweisen). Die Beschwerde ist in diesem Punkt unbegründet.
6. Die Beschwerde ist insgesamt unbegründet und abzuweisen. Bei diesem Verfahrensausgang sind die bundesgerichtlichen Kosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Der Beschwerdeführer ersucht um Gewährung der unentgeltlichen Rechtspflege. Da das Rechtsmittel von vornherein aussichtslos war, kann dem Gesuch nicht entsprochen werden (<ref-law>). Bei der Festsetzung der Gerichtsgebühr ist seinen finanziellen Verhältnissen Rechnung zu tragen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 1'600.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Bern, 3. Strafkammer, schriftlich mitgeteilt.
Lausanne, 3. November 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Der Gerichtsschreiber:
Schneider Keller