Sachverhalt:
A. X._ wird vorgeworfen, Y._ am 5. Mai 2003, ca. 23.00 Uhr, bis 6. Mai 2003, ca. 03.30 Uhr, gemeinsam mit A._ nach einem Barbesuch nicht wie abgemacht in das Restaurant B._ in Solothurn zurückgebracht, sondern sie gegen ihren Willen in seine Wohnung in Grenchen verbracht und dort sexuell missbraucht zu haben. Das Opfer habe A._ oral befriedigen müssen, während X._ den Geschlechtsverkehr an ihm vollzogen habe. Danach habe es den Penis von X._ in den Mund nehmen müssen, während A._ von hinten in es eingedrungen sei. Schliesslich habe es sich wieder auf X._ setzen müssen, um mit ihm den Geschlechtsverkehr bis zum Samenerguss zu vollziehen.
B. Das Obergericht des Kantons Solothurn sprach X._ im Berufungsverfahren am 31. Mai 2011 schuldig der Freiheitsberaubung und Entführung, der gemeinsamen sexuellen Nötigung und gemeinsamen Vergewaltigung (Dispositiv II Ziff. 1). Es verurteilte ihn zu einer Freiheitsstrafe von 35 1⁄2 Monaten als Zusatzstrafe zum Urteil der Staatsanwaltschaft des Kantons Solothurn vom 25. Februar 2010. Den Vollzug der Freiheitsstrafe schob es im Umfang von 26 1⁄2 Monaten unter Ansetzung einer Probezeit von zwei Jahren auf. Im Umfang von 9 Monaten erklärte es die Freiheitsstrafe als vollziehbar (Dispositiv II Ziff. 2). Das Begehren von X._ um Entschädigung für Nachteile wies es ebenso ab wie dasjenige um Parteientschädigung für das Verfahren vor zweiter Instanz (Dispositiv III Ziff. 2 und 3). Das Obergericht sprach Y._ eine Genugtuung von Fr. 15'000.-- zu, zahlbar je zur Hälfte durch X._ und A._, unter solidarischer Haftung für den ganzen Betrag, und erklärte die Beschuldigten gegenüber ihr für die Folgen aus dem Ereignis vom 5./6. Mai 2003 solidarisch zu 100 % schadenersatzpflichtig (Dispositiv III Ziff. 4 und 5). Es regelte die Kosten und Entschädigungen für das Verfahren vor erster und zweiter Instanz (Dispositiv III Ziff. 6-13).
C. Mit Beschwerde in Strafsachen beantragt X._, es seien die Entscheide des Obergerichts des Kantons Solothurn vom 31. Mai 2011 und des Amtsgerichts Solothurn-Lebern vom 26. Januar 2010 aufzuheben, und er sei von den Vorwürfen der Entführung und Freiheitsberaubung sowie der gemeinsamen sexuellen Nötigung und Vergewaltigung freizusprechen. Ihm sei eine Entschädigung für Nachteile in der Höhe von Fr. 10'000.-- oder nach richterlichem Ermessen zuzusprechen. Die Zivilansprüche seien abzuweisen bzw. auf den Zivilweg zu verweisen. Die Verfahrenskosten vor erster und zweiter Instanz habe der Staat zu tragen und es sei ihm für dieses Verfahren eine Parteientschädigung auszurichten. X._ ersucht ferner um unentgeltliche Rechtspflege und um aufschiebende Wirkung der Beschwerde.

Erwägungen:
1. Am 1. Januar 2011 trat die Schweizerische Strafprozessordnung (StPO; SR 312.0) in Kraft. Der Entscheid des Amtsgerichts Solothurn-Lebern erging am 26. Januar 2010. Das kantonale Verfahren samt der Berufung an die Vorinstanz richtet sich gemäss Art. 453 Abs. 1 StPO somit nach der Strafprozessordnung des Kantons Solothurn vom 7. Juni 1970 (aStPO/SO). Soweit der Beschwerdeführer die Schweizerische StPO für anwendbar erachtet und er sich im Rahmen seiner Beschwerde darauf beruft, ist er mit seinen Vorbringen nicht zu hören (Beschwerde, S. 25 f.).
2. Der Beschwerdeführer verlangt die Aufhebung des Entscheids des Amtsgerichts Solothurn-Lebern vom 26. Januar 2010. Auf die Beschwerde ist in diesem Punkt nicht einzutreten, denn Anfechtungsobjekt bildet einzig der kantonal letztinstanzliche Entscheid der Vorinstanz vom 31. Mai 2011 (<ref-law>).
3. Der Beschwerdeführer erachtet die polizeiliche Einvernahme von C._ vom 5. September 2006 nicht für verwertbar, weil ihm kein Konfrontationsrecht zugestanden worden sei (Beschwerde, S. 25 f.).
3.1 Der in Art. 6 Ziff. 3 lit. d EMRK garantierte Anspruch des Angeschuldigten, den Belastungszeugen Fragen zu stellen, ist ein besonderer Aspekt des Rechts auf ein faires Verfahren gemäss Art. 6 Ziff. 1 EMRK. Eine belastende Zeugenaussage ist grundsätzlich nur verwertbar, wenn der Beschuldigte wenigstens einmal während des Verfahrens angemessene und hinreichende Gelegenheit hatte, das Zeugnis in Zweifel zu ziehen und Fragen an den Belastungszeugen zu stellen. Dieser Anspruch wird als Konkretisierung des rechtlichen Gehörs (<ref-law>) auch durch <ref-law> gewährleistet (<ref-ruling> E. 2.2; <ref-ruling> E. 3.1 mit Hinweisen). Damit die Verteidigungsrechte gewahrt sind, muss der Beschuldigte namentlich in der Lage sein, die Glaubhaftigkeit einer Aussage prüfen und den Beweiswert in kontradiktorischer Weise auf die Probe und infrage stellen zu können (<ref-ruling> E. 2.2; <ref-ruling> E. 2.2; <ref-ruling> E. 4.2; je mit Hinweisen). Das kann entweder zum Zeitpunkt erfolgen, zu dem der Belastungszeuge seine Aussage macht, oder auch in einem späteren Verfahrensstadium (<ref-ruling> E. 2.2; <ref-ruling> E. 6b und 6c/aa mit Hinweisen).
3.2 Der Beschwerdeführer war anlässlich der polizeilichen Einvernahme von C._ vom 5. September 2006 nicht anwesend. Das Verfahren wurde in diesem Zeitpunkt gegen A._ und Unbekannt geführt. An der zweiten Befragung von C._ vom 4. November 2008 nahmen er und sein damaliger Rechtsvertreter teil. Zuvor hatten sie Einsicht in die Akten erhalten. Sie konnten daher in Kenntnis aller Einvernahmen gezielt Ergänzungsfragen stellen. Von dieser Möglichkeit machten sie Gebrauch (Entscheid, S. 24). Damit wurden die kantonalen Behörden dem Anspruch auf Konfrontation gerecht. Beide Befragungen vom 5. September 2006 und 4. November 2008 sind verwertbar. Die Frage, ob der ersten Einvernahme ausschlaggebende Bedeutung zukommt, stellt sich hier nicht. C._ wurde in beiden Einvernahmen zu den gleichen Themenkomplexen befragt. Er bestätigte in der Konfrontationseinvernahme ausdrücklich, dass die Beschwerdegegnerin 2 am Tatabend das Restaurant B._ zusammen mit dem Beschwerdeführer und A._ verlassen hatte, sie bei ihrer Rückkehr ein Bild bei sich hatte und einen traurigen Eindruck machte (kantonale Akten, Einvernahme vom 5. September 2006, act. 71 ff., 73 f.; kantonale Akten, Einvernahme vom 4. November 2008, act. 113 ff., 116-118).
3.3 Soweit der Beschwerdeführer rügt, die Befragung von C._ vom 5. September 2006 sei auch deshalb nicht verwertbar, weil dem Mitangeschuldigten A._ keine notwendige Verteidigung im Sinne von Art. 9 Abs. 1 lit. c StPO/SO bestellt wurde (Beschwerde, S. 25 f.), fehlt es ihm an einem rechtlich geschützten Interesse im Sinne von <ref-law>, weshalb auf das Vorbringen nicht einzutreten ist.
4. Der Beschwerdeführer wirft der Vorinstanz eine offensichtlich unrichtige, unvollständige und teilweise aktenwidrige Sachverhaltsfeststellung vor. Er verlangt einen Freispruch "in dubio pro reo".
4.1 Die Vorinstanz erachtet als erstellt, dass der Beschwerdeführer und A._ das Restaurant B._ in Solothurn zusammen mit der Beschwerdegegnerin 2 verliessen. Sie hätten zunächst gemeinsam ein weiteres Lokal besucht. Danach seien sie gegen den Willen der Beschwerdegegnerin 2 an den Wohnort des Beschwerdeführers in Grenchen gefahren. In der Wohnung habe dieser die Beschwerdegegnerin 2 geschlagen und sie gegen ihren Willen gemeinsam mit A._ ausgezogen. Beide Männer hätten in der Folge - in Abweichung zur Anklage und zu Gunsten des Beschwerdeführers - (nur) je einmal nicht einvernehmlichen Geschlechts- und Oralverkehr mit der Beschwerdegegnerin 2 gehabt (Entscheid, S. 35). Die Vorinstanz stützt sich hierfür im Wesentlichen auf die Aussagen der Beschwerdegegnerin 2, die konstant, in sich geschlossen und folgerichtig seien. Ihre Aussagen würden zudem untermauert durch die Aussagen von C._ sowie durch eine von der Beschwerdegegnerin 2 anlässlich ihrer Befragung vor dem Staatsanwalt mit bemerkenswerter Genauigkeit angefertigte Skizze der Wohnung des Beschwerdeführers. Hingegen seien die Aussagen des Beschwerdeführers und von A._ nicht glaubhaft. Sie bestritten den gemeinsamen Ausgang mit der Beschwerdegegnerin 2 und stellten ebenso einen gemeinsamen Aufenthalt in der Wohnung des Beschwerdeführers in Abrede. Im Weiteren widersprächen sie sich in Bezug auf ihre Beziehung zueinander (zum Beispiel mehrmals gemeinsam mit Frauen im Ausgang gewesen zu sein; sich nur vom Sehen her zu kennen). Die vom Beschwerdeführer ins Recht gelegten Unterlagen vermöchten schliesslich nicht zu belegen, dass er zur Tatzeit landesabwesend gewesen sei. Seine Anwesenheit in der Schweiz sei durch die Aussagen von C._ erstellt.
4.2 Die vorinstanzliche Sachverhaltsfeststellung kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>; vgl. auch Art. 105 Abs. 1 und 2 BGG). Offensichtlich unrichtig im Sinne von <ref-law> ist die Sachverhaltsfeststellung, wenn sie willkürlich ist (<ref-ruling> E. 2.4 S. 313 f. mit Hinweis; vgl. zum Begriff der Willkür <ref-ruling> E. 4.2 S. 560 mit Hinweisen). Die Rüge der Willkür muss in der Beschwerde anhand des angefochtenen Entscheids präzise vorgebracht und begründet werden, ansonsten darauf nicht eingetreten wird (<ref-law>; <ref-ruling> E. 4.2.3; <ref-ruling> E. 2.8).
4.3 Soweit der Beschwerdeführer sich nicht mit dem angefochtenen Entscheid auseinandersetzt, sondern lediglich darlegt, wie die Beweise aus seiner Sicht zu würdigen wären, sind seine Vorbringen rein appellatorisch. Das ist beispielsweise der Fall, soweit er behauptet, der fehlende "Belastungseifer" der Beschwerdegegnerin 2 sei nicht als Indiz für, sondern gegen die Glaubhaftigkeit ihrer Aussagen zu würdigen (Beschwerde, S. 7 ff., 28). Der Beschwerdeführer legt insoweit nur dar, wie der Umstand, dass das Opfer nicht aus eigener Initiative Anzeige erstattete und zunächst nicht über das Vorgefallene sprechen wollte, seiner Auffassung nach zu interpretieren wäre, nämlich in dem Sinne, dass eben nichts Strafbares vorgefallen sei. Den Nachweis, inwiefern die vorinstanzliche Beweiswürdigung diesbezüglich schlechterdings unhaltbar sein sollte, bleibt er schuldig. Entsprechendes gilt, wenn er geltend macht, die Gefühlsäusserungen der Beschwerdegegnerin 2 (Weinkrämpfe) während der ersten polizeilichen Einvernahme sprächen nicht für die Glaubhaftigkeit ihrer Aussagen, sondern hätten im Gegenteil einzig dazu gedient, Zeit zu gewinnen, um die eigenen Aussagen vorbereiten zu können (Beschwerde, S. 9 f.). Damit setzt der Beschwerdeführer wiederum nur seine Sicht der Dinge an die Stelle der vorinstanzlichen Beweiswürdigung, ohne Willkür aufzuzeigen. Nichts anderes tut er, wenn er geltend macht, die Schilderungen der eigenen Gefühle und psychischen Vorgänge der Beschwerdegegnerin 2 sprächen entgegen der Vorinstanz nicht für die Glaubhaftigkeit ihrer Aussagen, sondern dafür, dass nichts Spezielles vorgefallen sei, insbesondere keine Vergewaltigung und keine Freiheitsberaubung (Beschwerde, S. 18). Auch in Bezug auf die vorinstanzlichen Feststellungen zum Bild, welches die Beschwerdegegnerin 2 nach ihrer Rückkehr in die B._-Bar bei sich gehabt hatte und sie vom Beschwerdeführer in der Tatnacht erhalten haben will (Entscheid, S. 24 f.), verbleibt die Kritik im Bereich des Appellatorischen. Der Beschwerdeführer legt erneut nur dar, wie seine Aussagen sowie diejenigen der Beschwerdegegnerin 2 und von C._ richtigerweise zu würdigen wären, ohne sich substanziiert mit den vorinstanzlichen Erwägungen auseinanderzusetzen (Beschwerde, S. 14 f.). Auf diese und weitere gleichartige Vorbringen, mit welchen der Beschwerdeführer lediglich seine Sicht der Dinge darlegt, ohne sich hinreichend mit den Erwägungen im angefochtenen Entscheid zu befassen (vgl. Beschwerde, S. 16, 19 f., 20 f., 23 f., 26 f., 28 f., 29, 30, 33 ff.), ist nicht einzutreten.
4.4 An der Sache vorbei geht der Einwand, die Feststellungen der Vorinstanz zur Wahrnehmungs- und Einsichtsfähigkeit der Beschwerdegegnerin 2 liessen sich nicht auf die Akten stützen (Beschwerde, S. 6 f.). Die Vorinstanz folgert, es bestünden keine Hinweise darauf, dass die Beschwerdegegnerin 2 infolge übermässigen Alkoholkonsums in ihrer Fähigkeit zur Wahrnehmung und/oder Einsicht in Bezug auf die Ereignisse in der Tatnacht eingeschränkt gewesen sei. Sie stützt sich auf aktenkundige Umstände und Aussagen von Zeugen zum Zustand der Beschwerdegegnerin 2 vor und nach dem eigentlichen Tatgeschehen (Entscheid, S. 22).
4.5 Unbegründet ist der Vorwurf der unvollständigen Sachverhaltsfeststellung. Soweit der Beschwerdeführer rügt, die Vorinstanz habe einzelne Sachverhaltselemente nicht berücksichtigt, handelt es sich zum vornherein um solche von untergeordneter Bedeutung. Das Telefongespräch der Beschwerdegegnerin 2 mit D._ und der Zeitpunkt des Anrufs bilden abgesehen davon Teil der vorinstanzlichen Beweiswürdigung (Entscheid, S. 17, 25, 28). Dass die Beschwerdegegnerin 2 ihre Freundin D._ nicht bereits in der Zeit ihres Zusammenlebens über das Vorgefallene informierte, sondern erst später, brauchte die Vorinstanz nicht als Umstand zu würdigen, der gegen ihre Glaubwürdigkeit und die Glaubhaftigkeit ihrer Aussagen spricht (Beschwerde, S. 17, 22, 29 f.). Entsprechendes gilt für das Telefongespräch der Beschwerdegegnerin 2 mit C._ (Beschwerde, S. 22, 29). Es ist nicht aussergewöhnlich, dass Opfer von sexuellen Übergriffen unter Umständen lange nicht über den Missbrauch sprechen bzw. sprechen können. Davon kann ohne Willkür ausgegangen werden. Spekulativ ist das weitere Vorbringen des Beschwerdeführers, die beiden Telefonanrufe hätten der Beschwerdegegnerin 2 nur dazu gedient, allfällige Nachfragen des bereits informierten Ehemanns abzusichern (Beschwerde, S. 22, 29 f.).
4.6 Die Vorinstanz durfte ohne Willkür davon ausgehen, die Beschwerdegegnerin 2 sei vom Beschwerdeführer vor der Erzwingung des Beischlafs und des Oralverkehrs geschlagen worden (Beschwerde, S. 11, 20, 31 f.). Die Beschwerdegegnerin 2 gab im Rahmen sämtlicher Befragungen an, der Beschwerdeführer habe sie vor dem sexuellen Missbrauch ins Gesicht geschlagen. Nachdem sie auch vor Vorinstanz zunächst in diesem Sinne ausgesagt hatte, änderte sie ihre Aussagen im Verlaufe der Einvernahme insofern, als sie angab, nicht vor, sondern während der sexuellen Handlungen geschlagen worden zu sein. Die Vorinstanz zog sämtliche Aussagen der Beschwerdegegnerin 2 in die Beweiswürdigung mit ein (Entscheid, S. 23). Ihr Abstellen auf die anfänglichen und damit tatnäheren sowie mehrfach bestätigten Aussagen der Beschwerdegegnerin 2 ist nicht willkürlich. Das gilt auch in Bezug auf die Aussagen, sie sei von den Beschuldigten in die B._-Bar in Solothurn bzw. nach Solothurn zurückgebracht worden (Entscheid, S. 23; Beschwerde, S. 13). Vor diesem Hintergrund kann nicht gesagt werden, der vorinstanzliche Schluss, wonach die Beschwerdegegnerin 2 in den wesentlichen Punkten konstant ausgesagt habe, sei schlechterdings unhaltbar.
4.7 Nach dem Dafürhalten des Beschwerdeführers spricht das Fehlen von (Verletzungs-)Spuren im Gesicht der Beschwerdegegnerin 2 ebenso wie der Umstand, dass ihre Kleider nicht zerrissen waren bzw. C._ solches nicht konstatierte, gegen die Glaubhaftigkeit ihrer Aussagen (Beschwerde, S. 31). Schläge ins Gesicht führen nicht zwingend zu einem wahrnehmbaren äusseren Verletzungsbild wie zum Beispiel blauen Flecken, Kratzspuren oder Schwellungen. Die Beschwerdegegnerin 2 sprach im Weiteren nur davon, dass die Beschuldigten ihr in der Wohnung des Beschwerdeführers die Kleider weggerissen hätten. Es war nie die Rede davon, dass ihre Kleidungsstücke dabei zerrissen wären. Die Vorinstanz durfte deshalb willkürfrei annehmen, aus diesen Fakten liesse sich nichts zu Ungunsten der Beschwerdegegnerin 2 ableiten. Mit den entsprechenden Erwägungen im angefochtenen Entscheid (S. 32) setzt sich der Beschwerdeführer nicht auseinander.
4.8 Die Vorinstanz misst der Skizze, welche die Beschwerdegegnerin 2 über die Wohnung des Beschwerdeführers anfertigte, bei der Beweiswürdigung massgebliche Bedeutung zu. Sie sei mehr als viereinhalb Jahre nach der Tat bei der Einvernahme vor der Staatsanwaltschaft in der Lage gewesen, die fragliche Wohnung weitgehend zutreffend zu beschreiben. Die Richtigkeit der damals erstellten Skizze habe sich im Rahmen des vorinstanzlichen Augenscheins eindrücklich bestätigt. Es sei nicht nachvollziehbar, weshalb die Beschwerdegegnerin 2 diese Wohnung einschliesslich Korridorbereich beschreiben können sollte, wenn sie nie dort gewesen wäre (Entscheid, S. 23, 33). Der Beschwerdeführer wirft der Vorinstanz eine aktenwidrige Sachverhaltsfeststellung vor. Weder die Lage der Zimmer noch die Beschreibung der Möblierung entspräche den Tatsachen (Beschwerde, S. 11 f.). Der Einwand zielt ins Leere. Ein Vergleich der Skizze mit der bei den Akten liegenden Fotodokumentation der Wohnung ergibt eine Übereinstimmung in den wesentlichen Punkten (Raumanordnung, langer Eingang/Korridorbereich mit dem nach links abgehenden, fensterlosen Badezimmer mit Bad, WC und Dusche sowie dem zum Eingang hin schräg versetzten Wohn/Schlafraum; vgl. kantonale Akten, act. 102- 112). Die Vorinstanz durfte die Skizze willkürfrei als ein gewichtiges Indiz für die Glaubhaftigkeit der Aussagen der Beschwerdegegnerin 2 werten.
4.9 Der Beschwerdegegnerin 2 fielen die Narben von A._ an Oberarm und Rücken nicht auf. Die Vorinstanz sieht sich dadurch nicht veranlasst, die Glaubhaftigkeit der Aussagen des Opfers in Zweifel zu ziehen. Sie geht in der Hauptbegründung davon aus, dieses habe den Rücken des Genannten nicht gesehen, weil dieser von hinten in es eingedrungen sei. Die Vorinstanz erwägt zusätzlich, die Beschwerdegegnerin 2 habe sich in einer ohnmächtigen und schockierenden Situation befunden. Es könne deshalb nicht ohne weiteres angenommen werden, sie habe die Narben gesehen und im Gedächtnis gespeichert (Entscheid, S. 32). Mit der Hauptbegründung befasst sich der Beschwerdeführer nicht. Er macht lediglich geltend, die Beschwerdegegnerin 2 habe sich gemäss der Vorinstanz gut an die räumliche Situation in der Wohnung erinnern können. Entsprechend hätte sie bei gleicher Aufmerksamkeit auch die Narben auf dem Rücken von A._ erkennen müssen (Beschwerde, S. 32 f.). Damit kann Willkür nicht begründet werden.
4.10 Dass die Beschwerdegegnerin 2 nach dem Ereignis vom 5./6. Mai 2003 für kurze Zeit, höchstens für einige Tage, im Restaurant von A._ arbeitete, ist erstellt. Die Vorinstanz beurteilt dieses Verhalten als nur sehr schwer nachvollziehbar, auch unter Berücksichtigung der Erklärung der Beschwerdegegnerin 2, Geld benötigt zu haben. Dieser zu Ungunsten des Opfers sprechende Gesichtspunkt vermag die Glaubhaftigkeit seiner Aussagen nach der Auffassung der Vorinstanz im Rahmen der Gesamtbetrachtung indessen nicht umzustossen, weil gewichtige Indizien bestehen blieben, die ohne realen Erlebnishintergrund nicht denkbar wären (Entscheid, S. 27 und 33). Die vorinstanzliche Gewichtung des fraglichen Umstands ist verfassungsrechtlich nicht zu beanstanden. Dass die Beschwerdegegnerin 2 bei A._ nach den sexuellen Übergriffen kurz gearbeitet hat - was diese auf Nachfrage von sich aus einräumte (vgl. kantonale Akten, act. 51) -, betrifft nicht das Kerngeschehen, sondern einen Nebenumstand im Nachgang an das Ereignis vom 5./6. Mai 2003. Vor diesem Hintergrund musste die Vorinstanz diesem Gesichtspunkt keine "alles-entscheidende" Bedeutung zumessen, die das Beweisergebnis erschüttern würde.
4.11 Nach den Feststellungen der Vorinstanz brachte die Beschwerdegegnerin 2 ihren Willen, nicht in die Wohnung des Beschwerdeführers zu gehen und keinen Geschlechtsverkehr zu haben, ausdrücklich und mehrfach körperlich und verbal zum Ausdruck (Entscheid, S. 35). Als sie sich weigerte, mit den Männern den Beischlaf zu vollziehen, habe der Beschwerdeführer sie ins Gesicht geschlagen. Eingeschüchtert durch die Freiheitsberaubung und die Schläge habe sie keine Möglichkeit mehr gesehen, sich gegen die zwei an Körperkraft weit überlegenen Männer zur Wehr zu setzen (Entscheid, S. 37). Soweit der Beschwerdeführer behauptet, es fehlten jegliche Indizien dafür, dass das angebliche Geschehen gegen den Willen der Beschwerdegegnerin 2 stattgefunden habe, ist die Beschwerde unbegründet (Beschwerde, S. 16, 35). Seine allgemeinen Einwände - es bestünden massgebliche Zweifel, ob sich der Sachverhalt so wie von der Beschwerdegegnerin 2 geschildert abgespielt habe - sind nicht geeignet, die vorinstanzliche Beweiswürdigung in Frage zu stellen (Beschwerde, S. 35). Für die in der Beschwerde angedeutete These einer vorgeschobenen Vergewaltigungssituation finden sich keine Anhaltspunkte. Die Vorinstanz hat die Aussagen der Beschwerdegegnerin 2 willkürfrei als glaubhaft beurteilen dürfen.
4.12 Der Beschwerdeführer machte, als er anlässlich der polizeilichen Einvernahme vom 3. Juli 2007 mit den konkreten Vorhalten der Freiheitsberaubung und Vergewaltigung konfrontiert wurde, noch nicht geltend, zur Tatzeit im Ausland gewesen zu sein. Der Umstand, dass er die Dokumente betreffend seinen angeblichen Aufenthalt im Kosovo erst ein Jahr nach dieser Einvernahme kurz vor der erstinstanzlichen Hauptverhandlung zu den Akten reichte, durfte bei der Vorinstanz Skepsis erregen, weil die Erklärung des Beschwerdeführers nicht überzeugt, der gegen ihn erhobene Vorwurf sei ihm zu dieser Zeit derart absurd vorgekommen, dass er sich damit nicht ernsthaft habe auseinandersetzen müssen (Beschwerde, S. 37). Bei den eingereichten Unterlagen handelt es sich um Dokumente, welche eine Zahnbehandlung des Beschwerdeführers im Kosovo vom 4. bis 7. Mai 2003 belegen sollen (Entscheid S. 34 mit Hinweis auf "Specialistic Report" von Prof. E._ vom 27. August 2009 als Beleg für eine "Arbeitsabsenz gegenüber dem Arbeitgeber" in der Zeit vom 4. bis. 7 Mai 2003; Bestätigung von F._ vom 6. Dezember 2010, dass am 5. Mai 2003 Zahnröntgenbilder angefertigt wurden; Erklärung von G._ und H._ vom 28. September 2009, dass sich der Beschwerdeführer während der fraglichen Zeit bei ihnen aufgehalten hat). Weitere Unterlagen zum Aufenthalt des Beschwerdeführers im Kosovo in Bezug auf die Zahnbehandlung wie beispielsweise Krankengeschichte, Röntgenbilder oder Rechnungen konnten nicht beigebracht werden (Entscheid, S. 34). Vor diesem Hintergrund durfte die Vorinstanz den willkürfrei als glaubhaft beurteilten Aussagen der Beschwerdegegnerin 2 grösseren Beweiswert einräumen und annehmen, dass sich der Beschwerdeführer zur Tatzeit in der Schweiz befunden hatte, umso mehr als seine hiesige Anwesenheit durch den Zeugen C._ zwei Mal ausdrücklich bestätigt wurde (vorstehend E. 2.2; Entscheid, S. 24). Aufgrund dieses Beweisergebnisses durfte die Vorinstanz ohne Willkür in antizipierter Beweiswürdigung auf die beantragten Einvernahmen der Entlastungszeugen Prof. E._, F._ sowie G._ und H._ verzichten. Der Schluss, es seien hievon keine neuen sachrelevanten Erkenntnisse zu erwarten, ist nicht schlechthin unhaltbar. Die Abweisung der Beweisanträge verletzt weder das Willkürverbot noch den Gehörsanspruch des Beschwerdeführers.
5. Nach der Auffassung des Beschwerdeführers verletzen die Schuldsprüche wegen gemeinsamer sexueller Nötigung und Vergewaltigung Bundesrecht (Beschwerde, S. 43 f.). Seine Ausführungen zur rechtlichen Würdigung gehen an der Sache vorbei, weil sie sich nicht auf den von der Vorinstanz willkürfrei festgestellten Sachverhalt beziehen, sondern auf seine eigene Darlegung des Geschehens.
6. Die Begehren um Entrichtung einer Entschädigung, Abweisung der Zivilansprüche bzw. Verweisung auf den ordentlichen Zivilweg und Neuverlegung der Verfahrenskosten (Beschwerde, S. 44 ff.) begründet der Beschwerdeführer mit den beantragten Freisprechungen von allen Vorwürfen. Da es bei den Verurteilungen bleibt, ist darauf nicht weiter einzugehen.
7. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Das Gesuch um unentgeltliche Rechtspflege ist abzuweisen, da die Beschwerde von vornherein aussichtslos war (<ref-law>). Der finanziellen Lage des Beschwerdeführers ist bei der Festsetzung der Gerichtskosten Rechnung zu tragen (<ref-law>). Mit dem Entscheid in der Sache ist das Gesuch um aufschiebende Wirkung gegenstandslos geworden.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3. Die Gerichtskosten von Fr. 800.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Solothurn, Strafkammer, schriftlich mitgeteilt.
Lausanne, 12. März 2012
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Die Gerichtsschreiberin: Arquint Hill