Sachverhalt:
A. Der 1980 geborene X._ trat mit 18 Jahren erstmals strafrechtlich in Erscheinung und wurde unter anderem wegen strafbarer Handlungen gegen die sexuelle Integrität verurteilt (1999 wegen mehrfacher sexueller Nötigung und mehrfacher Vergewaltigung, 2000 wegen sexueller Handlungen mit einem Kind). Seit seiner Festnahme am 13. August 1999 befindet er sich im Haft- bzw. stationären Massnahmenvollzug. Gegenwärtig ist er im Therapiezentrum B._ untergebracht.
B. Auf Antrag der Vollzugs- und Bewährungsdienste des Kantons Luzern hin entschied das Kriminalgericht Luzern mit Urteil vom 12. Dezember 2007, die gegen X._ verhängte Massnahme nach Art. 43 Ziff. 1 Abs. 1 aStGB im Sinne von <ref-law> um drei Jahre zu verlängern.
C. Dagegen reichte X._ am 28. Januar 2008 Rekurs beim Obergericht des Kantons Luzern ein. Nach Eingang der von diesem in Auftrag gegebenen psychiatrischen Gutachtensergänzung vom 9. Juli 2008 und der hierzu ergangenen Stellungnahmen der Parteien wies das Obergericht den Rekurs am 21. August 2008 ab, soweit es darauf eintrat, und verlängerte die bestehende stationäre therapeutische Massnahme im Sinne von <ref-law> in Abänderung des erstinstanzlichen Entscheids auf unbestimmte Zeit, jedoch um höchstens 5 Jahre (Dispositiv-Ziffer 1 i.V.m. angefochtenem Urteil, S. 12 E. 2.5). Die Verfahrenskosten nahm es auf die Staatskasse (Dispositiv-Ziffer 2).
D. X._ wendet sich mit Beschwerde in Strafsachen an das Bundesgericht. Er beantragt, es sei Dispositiv-Ziffer 1 des angefochtenen Urteils des Obergerichts vom 21. August 2008 aufzuheben, und er sei aus dem stationären Vollzug der therapeutischen Massnahme bedingt zu entlassen. Eventuell sei die Verlängerung der stationären Massnahme um höchstens ein Jahr anzuordnen. Subeventuell sei die Streitsache zur neuen Beurteilung an die Vorinstanz zurückzuweisen. X._ ersucht ferner um die Gewährung der unentgeltlichen Rechtspflege und Verbeiständung.
E. Das Obergericht des Kantons Luzern schliesst in seiner Eingabe vom 15. Dezember 2008 auf Abweisung der Beschwerde. Die Staatsanwaltschaft des Kantons Luzern hat am 19. Dezember 2008 auf eine Stellungnahme zur Beschwerde verzichtet.

Erwägungen:
1. Der Beschwerdeführer befindet sich seit Jahren im stationären therapeutischen Massnahmenvollzug. Mit seiner Beschwerde wendet er sich im Wesentlichen gegen die angeordnete Verlängerung der Massnahme. Nach Ziff. 2 Abs. 1 der Schlussbestimmungen der Änderung vom 13. Dezember 2002 sind die Bestimmungen des neuen Rechts über die Massnahmen gemäss den Art. 56 - 65 StGB und über den Massnahmenvollzug gemäss <ref-law> auch auf die Täter anwendbar, die vor deren Inkrafttreten eine Tat begangen haben oder beurteilt worden sind. Da im zu beurteilenden Fall keine nachträgliche Verwahrung in Frage steht (vgl. Ziff. 2 Abs. 1 lit. a Schlussbestimmungen), ist in Bezug auf die Massnahmen das neue Recht anzuwenden. Die Frage des milderen Rechts gemäss <ref-law> stellt sich in diesem Zusammenhang nicht.
2. Nach <ref-law> beträgt der mit der stationären Behandlung verbundene Freiheitsentzug in der Regel höchstens fünf Jahre. Sind die Voraussetzungen für die bedingte Entlassung nach fünf Jahren noch nicht gegeben und ist zu erwarten, durch die Fortführung der Massnahme lasse sich der Gefahr weiterer mit der psychischen Störung des Täters in Zusammenhang stehender Verbrechen und Vergehen begegnen, so kann das Gericht auf Antrag der Vollzugsbehörde die Verlängerung der Massnahme um jeweils höchstens fünf Jahre anordnen.
2.1 Im Unterschied zum früheren Recht lässt sich eine stationäre therapeutische Behandlung über die Dauer von fünf Jahren hinaus nicht unbesehen fortführen. Die Massnahme bedarf nach Ablauf dieser Zeit vielmehr der gerichtlichen Überprüfung. Erweist sie sich, namentlich im Hinblick auf den psychischen Zustand des Betroffenen und dessen Rückfallgefährlichkeit, nach wie vor als notwendig und geeignet, kann sie um jeweils maximal fünf Jahre verlängert werden. Dabei ist, über die ordentliche Prüfung der Indikation der Massnahme hinaus, dem Prinzip der Verhältnismässigkeit verstärkt Beachtung zu schenken, zumal der Verlängerung der Massnahme im Grunde Ausnahmecharakter zukommt bzw. diese besonders zu begründen ist. Eine Begutachtung durch einen Sachverständigen ist dabei allerdings nicht zwingend erforderlich (vgl. <ref-law>; zum Ganzen HEER, Basler Kommentar, Strafgesetzbuch I, 2. Aufl., Basel, 2007, Art. 59 N. 126; dieselbe, Einige Schwerpunkte des neuen Massnahmenrechts, ZStrR 121/2003, S. 376 ff., 392; Trechsel/Pauen Borer, Schweizerisches Strafgesetzbuch, Praxiskommentar, Zürich 2008, Art. 59 N. 15).
2.1 Im Unterschied zum früheren Recht lässt sich eine stationäre therapeutische Behandlung über die Dauer von fünf Jahren hinaus nicht unbesehen fortführen. Die Massnahme bedarf nach Ablauf dieser Zeit vielmehr der gerichtlichen Überprüfung. Erweist sie sich, namentlich im Hinblick auf den psychischen Zustand des Betroffenen und dessen Rückfallgefährlichkeit, nach wie vor als notwendig und geeignet, kann sie um jeweils maximal fünf Jahre verlängert werden. Dabei ist, über die ordentliche Prüfung der Indikation der Massnahme hinaus, dem Prinzip der Verhältnismässigkeit verstärkt Beachtung zu schenken, zumal der Verlängerung der Massnahme im Grunde Ausnahmecharakter zukommt bzw. diese besonders zu begründen ist. Eine Begutachtung durch einen Sachverständigen ist dabei allerdings nicht zwingend erforderlich (vgl. <ref-law>; zum Ganzen HEER, Basler Kommentar, Strafgesetzbuch I, 2. Aufl., Basel, 2007, Art. 59 N. 126; dieselbe, Einige Schwerpunkte des neuen Massnahmenrechts, ZStrR 121/2003, S. 376 ff., 392; Trechsel/Pauen Borer, Schweizerisches Strafgesetzbuch, Praxiskommentar, Zürich 2008, Art. 59 N. 15).
2.2 2.2.1 Die gesetzlich geschaffene Möglichkeit der Massnahmenverlängerung knüpft mithin an zwei Bedingungen an. Sie erfordert zunächst, dass die Voraussetzungen für eine bedingte Entlassung nach <ref-law> noch nicht gegeben sind, dem Täter prospektiv also noch keine günstige Prognose gestellt werden kann (SCHWARZENEGGER ET AL., Strafrecht II, Strafen und Massnahmen, 8 Aufl., Zürich 2007, § 9 Rz. 1.22; HEER, a.a.O., Art. 62 N. 23).
2.2.2 Davon geht die Vorinstanz im angefochtenen Entscheid aus. Sie stützt sich dabei auf das psychiatrische Ergänzungsgutachten von Dr. med. A._vom 9. Juli 2008, welcher an der bisherigen Diagnose einer Persönlichkeitsstörung (F 70.0 nach ICD-10) ausdrücklich festhält, das Ausmass dieser Störung trotz Behandlungsfortschritten nach wie vor als erheblich bezeichnet und von einer insgesamt nicht unbeträchtlichen Wahrscheinlichkeit der Begehung weiterer Straftaten wie etwa Sexual-, Vermögens- sowie Betäubungsmitteldelikte ausgeht (Gutachten, S. 10-12). Deswegen und insbesondere gestützt auch auf den Umstand, dass der Beschwerdeführer laut dem Gutachter ohne entsprechende Vorbereitungen für ein selbständiges Leben in Freiheit zurzeit überfordert wäre, gelangt die Vorinstanz zum Schluss, dass gegenwärtig nicht auf eine Bewährung des Beschwerdeführers in Freiheit geschlossen werden könne. Die Voraussetzungen für eine bedingte Entlassung seien damit zurzeit (noch) nicht gegeben.
2.2.3 Dass und inwiefern die Vorinstanz im angefochtenen Entscheid von der gutachterlichen Einschätzung abweicht, indem sie etwa die psychiatrische Diagnose unzulässigerweise ausgeweitet oder die ärztliche Beurteilung der Rückfallgefahr unzutreffend wiedergegeben haben soll, ist nicht erkennbar. Entgegen der Beschwerde hat die Vorinstanz insbesondere nicht verkannt, dass laut Gutachter keine konkreten Hinweise auf Rückfälle in Bezug auf Sexualdelikte bestehen. Sie hat diesen Umstand aber nachvollziehbar mit dem mittlerweile neun Jahre dauernden Vollzug erklärt. Ebenso wenig übersieht sie, dass sich die aufgrund des beim Beschwerdeführer festgestellten Klinefelter-Syndroms stetig abnehmende Testosteronproduktion bei der Rückfallgefahr hinsichtlich Sexualdelikte günstig auswirken dürfte. Sie betont aber insoweit zu Recht, dass der Zeitpunkt, in welchem diese Produktion zum Erliegen komme, auch nach dem Gutachter weder bestimmt noch exakt bestimmbar sei. Auch was die Einschätzung der Rückfallgefahr in Bezug auf Verstösse gegen das Betäubungsmittelgesetz und bei Vermögensdelikten angeht, legt die Vorinstanz ihrer Beurteilung die Ausführungen des Gutachters zugrunde, welcher in dieser Hinsicht weiterhin von einer schwer einschätzbaren Gefahr und damit von einem nicht unbeträchtlichen Risiko weiterer solcher Straftaten ausgeht. Schliesslich lässt die Vorinstanz bei der Prognosebeurteilung entgegen der Meinung der Verteidigung auch die Erkenntnisse aus den positiv verlaufenen Urlauben nicht unberücksichtigt, zumal die dahingehenden Auskünfte des Vollzugsleiters und des leitenden Arztes der forensisch-psychiatrischen Dienste der Psychiatrischen Klinik Solothurn in die von der Vorinstanz übernommene gutachterliche Beurteilung des Rückfallrisikos eingeflossen sind (vgl. Gutachten, S. 9).
2.2.4 Vor diesem Hintergrund, d.h. insbesondere aufgrund des psychischen Gesundheitszustands des Beschwerdeführers, seiner noch ungenügenden Selbständigkeit für ein Leben in Freiheit und des insgesamt nicht unwahrscheinlichen Risikos weiterer Verbrechen und Vergehen hat die Vorinstanz die Voraussetzungen für eine bedingte Entlassung vorliegend verneinen dürfen, da unter den gegebenen Umständen nicht davon ausgegangen werden kann, dass sich der Beschwerdeführer gegenwärtig in Freiheit bewähren wird. Der angefochtene Entscheid verletzt insoweit kein Bundesrecht. Der Beschwerdeführer dringt mit seinem Hauptantrag auf bedingte Entlassung aus der Massnahme folglich nicht durch. Die Beschwerde erweist sich in diesem Punkt als unbegründet.
2.2.4 Vor diesem Hintergrund, d.h. insbesondere aufgrund des psychischen Gesundheitszustands des Beschwerdeführers, seiner noch ungenügenden Selbständigkeit für ein Leben in Freiheit und des insgesamt nicht unwahrscheinlichen Risikos weiterer Verbrechen und Vergehen hat die Vorinstanz die Voraussetzungen für eine bedingte Entlassung vorliegend verneinen dürfen, da unter den gegebenen Umständen nicht davon ausgegangen werden kann, dass sich der Beschwerdeführer gegenwärtig in Freiheit bewähren wird. Der angefochtene Entscheid verletzt insoweit kein Bundesrecht. Der Beschwerdeführer dringt mit seinem Hauptantrag auf bedingte Entlassung aus der Massnahme folglich nicht durch. Die Beschwerde erweist sich in diesem Punkt als unbegründet.
2.3 2.3.1 Damit eine stationäre Massnahme verlängert werden kann, muss sodann - im Sinne von <ref-law> - erwartet werden können, dass sich durch die Fortführung der Massnahme der Gefahr weiterer mit der psychischen Störung des Täters in Zusammenhang stehender Verbrechen und Vergehen begegnen lasse.
2.3.2 Auch dieses Erfordernis hat die Vorinstanz, ohne Bundesrecht zu verletzen, entgegen der Ansicht des Beschwerdeführers als erfüllt betrachten dürfen. Zwar trifft zu, dass der Gutachter das Fortführen der stationären Massnahme im heutigen Setting für sinnlos hält. Damit ist aber, wie die Vorinstanz zu Recht darlegt, lediglich die gegenwärtige spezifische Ausgestaltung der Behandlung gemeint. Die stationäre Massnahme als solche hält der Gutachter nach wie vor für notwendig und geeignet, um die psychische Störung des Beschwerdeführer im Hinblick auf die Verbesserung der Legalprognose zu behandeln, weist er in seiner Beurteilung doch ausdrücklich auf "die noch zu leistende Arbeit" im stationären Massnahmenvollzug hin, bevor an eine "probeweise Entlassung" gedacht werden könne (vgl. Gutachten, S. 12 oben). Der angefochtene Entscheid verletzt mithin auch in dieser Hinsicht kein Bundesrecht.
2.4 Sind wie hier die gesetzlichen Voraussetzungen gegeben, so kann das zuständige Gericht die Massnahme nach dem Gesetzeswortlaut um jeweils höchstens fünf Jahre verlängern. Aus dieser Formulierung ergibt sich zunächst, dass eine Massnahmenverlängerung selbst bei Vorliegen der in <ref-law> genannten Voraussetzungen nicht zwingend erfolgen muss ("Kann-Vorschrift"). Das Gericht hat insofern abzuwägen, ob die vom Betroffenen ausgehende Gefahr den mit der Verlängerung der Massnahme verbundenen Eingriff in seine Freiheitsrechte zu rechtfertigen vermag. Dabei kann nur die Gefahr relativ schwerer Delikte eine Verlängerung rechtfertigen (TRECHSEL/PAUEN BORER, a.a.O., Art. 59 N. 15; STRATENWERTH, Schweizerisches Strafrecht, Allgemeiner Teil II, Strafen und Massnahmen, 2. Aufl., Basel 2006, § 9 Rz 40). Das Verhältnismässigkeitsprinzip verlangt jedoch nicht nur in Bezug auf die Anordnung der Massnahmenverlängerung als solche Beachtung, sondern auch hinsichtlich ihrer Dauer (<ref-law>). Nach dem Gesetzeswortlaut darf die Massnahme, wie erwähnt, um höchstens fünf Jahre verlängert werden. Daraus folgt unmissverständlich, dass im Einzelfall auch eine Verlängerungsdauer von weniger als fünf Jahren in Frage kommen kann.
2.4.1 Die Vorinstanz erwägt, dass vorliegend eine Verlängerung anzuordnen ist. In Anbetracht der nicht unbeträchtlichen Wahrscheinlichkeit und Schwere weiterer Straftaten sei der mit einer Verlängerung der Massnahme verbundene Eingriff in die Persönlichkeitsrechte des Beschwerdeführers derweilen noch verhältnismässig. Das für die Massnahmenverlängerung zuständige Gericht habe indessen keine konkrete Dauer der Massnahme festzulegen. Dies ergebe sich nicht nur aus dem Wortlaut von <ref-law>, sondern auch daraus, dass Massnahmen grundsätzlich bis zur Beseitigung der vom Täter ausgehenden Gefahr, also auf unbestimmte Zeit, ausgesprochen würden. Gegen die gerichtliche Festlegung einer konkreten Dauer der Massnahmenverlängerung spreche auch die vom Gesetzgeber gewollte Kompetenzordnung. Während die Anordnung einer Verlängerung oder Nicht-Verlängerung einer stationären Massnahme dem Gericht obliege, sei für die Entlassung aus der Massnahme oder für deren Aufhebung die Vollzugsbehörde verantwortlich. Komme das zuständige Gericht zur Auffassung, dass die stationäre Massnahme zu verlängern sei, könne es deshalb nur die in <ref-law> angegebene Höchstdauer von fünf Jahren aussprechen und müsse dabei selbst eine wie im zu beurteilenden Fall gutachterlich empfohlene kürzere Dauer unberücksichtigt lassen. Die vorliegende Massnahme sei deshalb auf unbestimmte Zeit, jedoch um höchstens fünf Jahre zu verlängern.
2.4.2 Mit dieser Auffassung verletzt die Vorinstanz Bundesrecht. Zwar ist mit ihr davon auszugehen, dass die vom Beschwerdeführer ausgehende Gefahr weiterer Straftaten (insbesondere im Bereich der Sexualdelinquenz) die mit der Anordnung der Massnahmenverlängerung einhergehenden Freiheitsbeschränkungen mit Blick auf das Schutzbedürfnis der Allgemeinheit gegenwärtig grundsätzlich noch zu rechtfertigen vermag. Insoweit ist der angefochtene Entscheid nicht zu beanstanden. Jedoch kann der Vorinstanz nicht gefolgt werden, soweit sie sich auf den Standpunkt stellt, Massnahmen seien nach <ref-law> in jedem Fall um die Höchstdauer von fünf Jahren zu verlängern. Diese Auffassung lässt sich zum einen weder aus der den Massnahmen eigenen spezialpräventiven Zielsetzung noch aus der gesetzlichen Kompetenzordnung im Verfahren um die Massnahmenbeendigung herleiten. Zum anderen steht sie im Widerspruch mit dem Gesetzeswortlaut, der im Hinblick auf Sinn und Zweck der Regelung nicht anders verstanden werden kann, als dass die Massnahme im Einzelfall auch um weniger als fünf Jahre verlängert werden darf. Insoweit hat die Vorinstanz ihr Ermessen nicht ausgeschöpft, was als Ermessensunterschreitung Bundesrecht verletzt. Der angefochtene Entscheid ist daher aufzuheben und die Sache an die Vorinstanz zur Neuentscheidung zurückzuweisen. Dabei wird sie im Zusammenhang mit der im zu beurteilenden Fall konkret anzuordnenden Verlängerungsdauer sämtliche in dieser Hinsicht rechtsrelevanten Umstände berücksichtigen müssen, insbesondere auch die vom Gutachter in dieser Hinsicht abgegebene Empfehlung, die stationäre Massnahme (lediglich) um ein Jahr zu verlängern. Bei dieser Rechtslage erübrigt es sich, auf die vom Beschwerdeführer geltend gemachte Missachtung des Verbots der "reformatio in peius" einzugehen.
3. Damit ist die Beschwerde teilweise gutzuheissen, der angefochtene Entscheid vom 21. August 2008 aufzuheben und die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Im Übrigen ist die Beschwerde abzuweisen.
Bei diesem Ausgang des Verfahrens sind, soweit der Beschwerdeführer obsiegt, keine Kosten zu erheben (Art. 66 Abs. 1 und 4 BGG), und ist ihm eine angemessene Parteientschädigung zuzusprechen (<ref-law>). Insofern wird das Gesuch um unentgeltliche Rechtspflege gegenstandslos. Im Umfang seines Unterliegens trägt der Beschwerdeführer die Kosten des Verfahrens. Das Gesuch um unentgeltliche Rechtspflege kann, soweit es nicht gegenstandslos geworden ist, gutgeheissen werden, da die Beschwerde nicht aussichtslos war (Art. 64 Abs. 1 und 2 BGG). In diesem Umfang werden keine Kosten erhoben, und wird dem Vertreter des Beschwerdeführers aus der Bundesgerichtskasse eine angemessene Entschädigung ausgerichtet (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen, das Urteil des Obergerichts des Kantons Luzern vom 21. August 2008 aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen; im Übrigen wird die Beschwerde abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege wird, soweit es nicht gegenstandslos geworden ist, gutgeheissen.
3. Es werden keine Kosten erhoben.
4. Der Kanton Luzern hat den Rechtsvertreter des Beschwerdeführers für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
5. Dem Rechtsvertreter des Beschwerdeführers wird für das bundesgerichtliche Verfahren eine Entschädigung von Fr. 1'000.-- aus der Bundesgerichtskasse ausgerichtet.
6. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Luzern, II. Kammer, schriftlich mitgeteilt.
Lausanne, 8. Januar 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Schneider Arquint Hill