Sachverhalt:
A. A.a A._ (Beschwerdeführerin 1) mit Wohnsitz in Aserbaidschan, ist eine professionelle Ringerin. Sie ist seit Juli 2007 Mitglied des Aserbaidschanischen Ringerverbands. Davor war sie Mitglied des Ukrainischen Ringerverbands.
Die Azerbaijan Wrestling Federation (AWF; Beschwerdeführer 2) ist der Aserbaidschanische nationale Ringerverband, verantwortlich für die Förderung und Entwicklung des Ringsportes in Aserbaidschan. Er überwacht den Ringsport insbesondere im Hinblick auf die Einhaltung der anwendbaren Regeln.
Die World Anti-Doping Agency (WADA; Beschwerdegegnerin 1) ist eine Stiftung nach schweizerischem Recht mit Sitz in Lausanne. Zweck der Beschwerdegegnerin 1 ist der weltweite Kampf gegen Doping im Sport in allen seinen Formen.
Die International Federation of Associated Wrestling Styles (FILA; Beschwerdegegner 2) ist der internationale Verband der vereinten Ringstile. Er ist verantwortlich für die Förderung und Entwicklung des Ringsportes auf internationaler Ebene und überwacht den Ringsport insbesondere auf die Einhaltung der anwendbaren Regeln. Er ist ein Verein nach schweizerischem Recht.
A.b Die Beschwerdeführerin 1 nahm am 25. und 26. April 2006 an der Europameisterschaft im Ringen in Moskau teil. Sie gewann den Wettbewerb in der Kategorie Damen, 48 kg. Am 26. April 2007 wurde sie einer Dopingkontrolle unterzogen. Diese ergab einen positiven Befund mit dem unzulässigen Diuretikum Furosemid.
Mit Entscheid vom 31. Mai 2006 sperrte der Sportrichter der FILA die Beschwerdeführerin 1 für ein Jahr.
Die FILA stellte der WADA am 9. Juni 2006 eine Kopie dieses Entscheids zu. Diese teilte mit, dass sie eine Sperre von einem Jahr als nicht regelkonform erachte und eine Anfechtung des Entscheids beim TAS erwäge. Daraufhin informierte die FILA die WADA, dass sie auf den Entscheid zurückkommen wolle.
Am 4. September 2006 erliess der Sportrichter der FILA einen neuen Entscheid und verhängte gegen die Beschwerdeführerin 1 eine zweijährige Sperre.
A.c Der Ukrainische Ringerverband teilte der FILA mit Schreiben vom 23. November 2006 mit, dass er weitere Abklärungen getätigt habe. Danach habe eine Freundin und frühere Konkurrentin der Beschwerdeführerin 1, B._, gestanden, die verbotene Substanz in eine Mineralwasserflasche gegeben zu haben, aus der die Beschwerdeführerin 1 am 24. April 2006 beim Nachtessen im Hotel "C._" in Moskau getrunken habe. Wegen dieses Verhaltens wurde B._ in der Folge lebenslänglich gesperrt. In Anbetracht dieser neuen Erkenntnisse ersuchte der Ukrainische Ringerverband darum, die gegen die Beschwerdeführerin 1 verhängte Sanktion zu überdenken.
Am 14. Dezember 2006 unterbreitete der FILA Präsident den Mitgliedern der FILA Federal Appeal Commission dieses Vorbringen und führte unter anderem aus:
" ... Mrs. A._ and the President of the Ukrainian Wrestling Federation are now appealing against this decision as new developments came to light which enable us to review this judgement. [...] Considering this claim as unquestionable, we have decided to submit this appeal to your kind assessment and to ask you to pronounce in favour of her rehabilitation, notwithstanding the start of legal proceedings against Mrs. B._."
Am 18. Juni 2007 gelangte der Ukrainische Ringerverband erneut an die FILA und bat um eine Reduktion der Sperre.
Mit Fax vom 20. Juni 2007 schrieb der Präsident der FILA an den Ukrainischen Ringerverband, dass er den Fall nochmals geprüft habe und als FILA Präsident eine Reduktion der Sperre auf 15 Monate befürworte. Demnach sei die Beschwerdeführerin berechtigt, ab 26. Juli 2007 an allen nationalen und internationalen Meisterschaften teilzunehmen.
A.d Am 21. September 2007 informierte eine anonyme Person die WADA, dass die Beschwerdeführerin 1 im September 2007 an den Weltmeisterschaften in Baku teilgenommen habe. Sie erreichte dort den 7. Rang und qualifizierte sich damit zur Teilnahme an den Olympischen Spielen 2008 in Peking.
Gleichentags ersuchte die WADA den FILA Generalsekretär um eine Erklärung. Dieser teilte ihr am 26. September 2006 mit, dass aufgrund eines Appeals des Ukrainischen Ringerverbands die FILA Federal Appeal Commission die Sperre auf 15 Monate reduziert habe. Gleichentags verlangte die WADA die Zustellung einer Kopie des Entscheids und eine detailliertere Erklärung.
Mit Schreiben vom 28. September 2007, unterzeichnet vom FILA Präsidenten und vom FILA Generalsekretär, erklärte die FILA der WADA den Entscheidungsprozess wie folgt:
" ... En effet, suite au recours de l'Ukraine du 23 novembre 2006 (...), la Commission d'Appel a été consultée par courier et la majorité des membres de la Commission d'Appel s'est prononcé pour une réduction de la peine. La Commission n'étant pas unanime et malgré que l'unanimité n'était pas requise pour une décision d'appel, la réduction de sanction n'a pas été communiquée à l'athlète immédiatement mais après la réunion tenue au siège de la FILA lors de l'inauguration le 15 juin 2007 où l'unanimité a été acquise, la décision à prendre n'ayant pas un degré d'urgence car l'objectif de la lutteuse étant le Championnat du Monde en septembre 2007. Suite à cette réunion la notification de réduction de peine a été notifiée par courrier du 20 juin 2007. (...)"
Am 1. Oktober 2007 ersuchte die WADA um weitere Erklärungen. Am 3. Oktober 2007 teilte der FILA Generalsekretär der WADA mit, dass der FILA Präsident gestützt auf Art. 60 der FILA Disciplinary Regulations zur Gewährung einer Begnadigung und zur Strafreduktion zuständig sei.
B. Die Beschwerdegegnerin 1 erklärte am 11. Oktober 2007 beim Tribunal Arbitral du Sport (TAS) Berufung gegen den Entscheid, der der Beschwerdeführerin 1 am 20. Juni 2007 mitgeteilt worden war, unabhängig davon, ob er von der FILA Federal Appeal Commission oder vom FILA Präsidenten getroffen worden sei. Sie verlangte eine zweijährige Sperrung der Beschwerdeführerin 1.
Das TAS setzte sich zusammen aus Dr. Christian Duve (Präsident), Quentin Byrne-Sutton und Türker Arslan.
Mit Schiedsentscheid vom 17. Juli 2008 bejahte das TAS seine Zuständigkeit zur Beurteilung der Berufung der Beschwerdegegnerin 1. In Gutheissung der Berufung hob es den Entscheid der FILA vom 20. Juni 2007 auf und verhängte gegen die Beschwerdeführerin 1 eine zweijährige Sperre vom 26. April 2006 bis zum 25. April 2008.
C. Die Beschwerdeführer beantragen mit Beschwerde in Zivilsachen, den Schiedsentscheid des TAS vom 17. Juli 2008 vollumfänglich aufzuheben und festzustellen, dass das TAS nicht zuständig sei, über den Appeal der WADA vom 11. Oktober 2007 gegen den Entscheid des FILA Präsidenten vom 20. Juni 2007 zu entscheiden. Ferner sei festzustellen, dass der Entscheid des FILA Präsidenten vom 20. Juni 2007 betreffend A._ in Rechtskraft erwachsen ist und die Beschwerdeführerin 1 15 Monate, nämlich vom 26. April 2006 bis 26. Juli 2007, von der Teilnahme an jeglichen nationalen und internationalen Ringerwettbewerben ausgeschlossen bzw. gesperrt war.
Die Beschwerdegegnerin 1 beantragt, die Beschwerde abzuweisen. Der Beschwerdegegner 2 liess sich nicht vernehmen. Das TAS verzichtete auf eine Vernehmlassung.
D. Mit Präsidialverfügung vom 26. November 2008 wurde das Gesuch der Beschwerdegegnerin 1 um Sicherstellung einer allfälligen Parteientschädigung für den Betrag von Fr. 5'000.-- gutgeheissen.

Erwägungen:
1. Das vorliegende Urteil ist den Parteien und der Vorinstanz am 17. März 2009 im Dispositiv eröffnet worden. Infolge eines Versehens wurde dabei im Urteilskopf Frau Bundesrichterin Klett als mitwirkende Präsidentin aufgeführt statt Herr Bundesrichter Corboz, der beim Urteil als präsidierendes Mitglied der I. zivilrechtlichen Abteilung mitgewirkt hatte. In der vorliegenden vollständigen Ausfertigung des Urteils ist dieses Versehen berichtigt.
2. Zum Verfahrensantrag der Beschwerdeführer, es sei ihnen Gelegenheit einzuräumen, zu allfälligen Eingaben und Antworten der Beschwerdegegner sowie zu einer allfälligen Vernehmlassung des TAS Stellung nehmen zu können, ist festzuhalten, dass das Bundesgericht in der Regel keinen zweiten Schriftenwechsel anordnet (<ref-law>). Den Beschwerdeführern stand es jedoch frei, sich zur Antwort der Beschwerdegegnerin 1 - unverzüglich - nochmals zu äussern (<ref-ruling> E. 2.2). Von dieser Möglichkeit haben sie keinen Gebrauch gemacht.
3. Der angefochtene Schiedsentscheid ist in englischer Sprache verfasst. Die Beschwerdeführer bedienen sich im bundesgerichtlichen Verfahren der deutschen, die Beschwerdegegnerin 1 bedient sich der französischen Sprache. Da die Sprache des angefochtenen Entscheids keine Amtssprache ist, ergeht das Bundesgerichtsurteil praxisgemäss in der Sprache der Beschwerde (vgl. <ref-law>).
4. Unter den Voraussetzungen der Art. 190-192 IPRG ist gegen Entscheide von Schiedsgerichten die Beschwerde in Zivilsachen zulässig (<ref-law>).
Der Sitz des Schiedsgerichts befindet sich vorliegend in Lausanne. Die Beschwerdeführer haben ihren Wohnsitz bzw. Sitz nicht in der Schweiz, sondern in Aserbaidschan. Da die Parteien die Bestimmungen des 12. Kapitels des IPRG nicht schriftlich ausgeschlossen haben, gelangen diese zur Anwendung (Art. 176 Abs. 1 und 2 IPRG).
Nach <ref-law> prüft das Bundesgericht nur die Rügen, die in der Beschwerde vorgebracht und begründet worden sind. Dabei gelten nach wie vor die strengen Begründungsanforderungen, die das Bundesgericht unter der Herrschaft von Art. 90 Abs. 1 lit. b OG stellte (vgl. <ref-ruling> E. 1c S. 53), da das BGG insofern keine Änderungen vornehmen wollte (<ref-ruling> E. 5).
Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den das Schiedsgericht festgestellt hat (<ref-law>). Es kann dessen Sachverhaltsfeststellung nicht berichtigen oder ergänzen, selbst wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>, der die Anwendbarkeit von <ref-law> ausschliesst). Allerdings kann das Bundesgericht die tatsächlichen Feststellungen des angefochtenen Schiedsentscheids, wie bereits im altrechtlichen Verfahren der staatsrechtlichen Beschwerde, prüfen, wenn gegenüber diesen zulässige Rügen im Sinne von <ref-law> vorgebracht oder ausnahmsweise im Rahmen der Beschwerde in Zivilsachen nach <ref-law> zulässige Noven berücksichtigt werden (Urteil 4A_128/2008 vom 19. August 2008 E. 2.4, in: Bull. ASA 4/2008 777; ferner: <ref-ruling> E. 5.2.2; <ref-ruling> E. 2a S. 54).
5. Die Beschwerdeführer bestreiten gestützt auf <ref-law> die Zuständigkeit des TAS.
5.1 Das Bundesgericht prüft die Zuständigkeitsrüge nach <ref-law> in rechtlicher Hinsicht frei, einschliesslich materiellrechtliche Vorfragen, von deren Beantwortung die Zuständigkeit abhängt. Allerdings überprüft das Bundesgericht die tatsächlichen Feststellungen des angefochtenen Schiedsentscheids auch im Rahmen der Zuständigkeitsrüge nur, wenn gegenüber diesen Sachverhaltsfeststellungen zulässige Rügen im Sinne von <ref-law> vorgebracht oder ausnahmsweise Noven berücksichtigt werden (<ref-ruling> E. 3.1; <ref-ruling> E. 5 S. 141; <ref-ruling> E. 5.2.2 S. 733 mit Hinweisen).
5.2 Das TAS bejahte seine Zuständigkeit gestützt auf R47 des Code de l'arbitrage en matière de sport (TAS-Code) und Art. 13.2.1 der FILA Anti-Doping Regulations.
R47 TAS-Code lautet, soweit hier von Interesse:
"Un appel contre une décision d'une fédération, association ou autre organisme sportif peut être déposé au TAS si les statuts ou règlements dudit organisme sportif le prévoient (...) et dans la mesure aussi où l'appelant a épuisé les voies de droit préalables à l'appel dont il dispose en vertu des statuts ou règlements dudit organisme sportif."
Art. 13 der FILA Anti-Doping Regulations sieht vor:
"13.2.1 Appeals from international level athletes
In cases arising from competition in an international event or in cases involving international level athletes, the FILA Sporting Judge's decision may be appealed to the FILA's Federal Appeal Commission. In case of disagreement about the decision, the parties may appeal exclusively to the Court of Arbitration for Sport (CAS), in accordance with the provisions applicable before such court. The CAS decision is executory and final.
13.2.3 Persons authorized to appeal
In cases mentioned in Article 13.2.1, at the first level of appeal, the following parties shall have the right to appeal to FILA Federal Appeal Commission:
[...]
and
e) WADA."
5.3 Die Beschwerdeführer machen geltend, nach der Schiedsklausel von Art. 13.2.1 der FILA Anti-Doping Regulations könnten nur Entscheide der FILA Federal Appeal Commission vor dem TAS angefochten werden, nicht jedoch Entscheide des FILA Präsidenten. Der von der Beschwerdegegnerin 1 beim TAS angefochtene Entscheid vom 20. Juni 2007 sei vom FILA Präsidenten gefällt worden. Dieser könne beim TAS nicht angefochten werden. Folglich habe das TAS seine Zuständigkeit zu Unrecht bejaht.
5.4 Diese Argumentation scheitert bereits an der Bindung des Bundesgerichts an die tatsächlichen Feststellungen der Vorinstanz (<ref-law>; Erwägungen 3 und 4.1 vorne). Entgegen der Meinung der Beschwerdeführer ist die Frage, ob der angefochtene Entscheid betreffend Reduktion der Sperre von der FILA Federal Appeal Commission oder vom FILA Präsidenten ausging, keine Rechtsfrage, sondern eine Tatfrage. Das TAS kam in Würdigung der Akten, namentlich des Briefes der FILA vom 28. September 2007 (vgl. vorne Erwägung Ad), in tatsächlicher Hinsicht zum Schluss, dass die FILA Federal Appeal Commission den Entscheid, die Sperre der Beschwerdeführerin 1 von zwei Jahren auf 15 Monate zu verkürzen, anlässlich ihres Treffens nach der Inauguration vom 15. Juni 2007 gefällt habe. Dieser Entscheid sei den Betroffenen durch den FILA Präsidenten in seinem Schreiben vom 20. Juni 2007 eröffnet worden.
5.5 Die Beschwerdeführer machen in diesem Zusammenhang eine Verletzung des Grundsatzes des rechtlichen Gehörs nach <ref-law> geltend. Falls von einer Tatfrage auszugehen sei, so wäre die Feststellung des TAS, der Entscheid vom 20. Juni 2007 sei von der FILA Federal Appeal Commission gefällt worden, offensichtlich falsch und aktenwidrig. Denn aus dem Entscheid vom 20. Juni 2007, der dem TAS als Akte vorgelegen habe, gehe eindeutig hervor, dass er vom FILA Präsidenten gefällt worden sei.
Dazu ist festzuhalten, dass in einer falschen oder aktenwidrigen Feststellung für sich allein keine Verletzung des Anspruchs auf rechtliches Gehör liegt. Eine solche ist nur bei einer formellen Rechtsverweigerung gegeben, mithin wenn der Partei die Möglichkeit genommen wurde, am Prozess teilzunehmen, ihn zu beeinflussen und ihren Standpunkt einzubringen (<ref-ruling> E. 5.2; <ref-ruling> E. 2b-e).
Solches zeigen die Beschwerdeführer nicht auf. Vielmehr hatten sie ausreichend Gelegenheit, sich zur Frage, von welchem Organ der FILA der angefochtene Entscheid getroffen worden war, zu äussern. Das TAS hat sämtliche Akten, darunter namentlich das Schreiben des FILA Präsidenten vom 20. Juni 2007, berücksichtigt und gewürdigt. Dass es bei dieser Würdigung zu einem anderen Schluss gelangte als die Beschwerdeführer, bedeutet keine Verletzung des Anspruchs auf rechtliches Gehör.
Das Bundesgericht hat demnach davon auszugehen, dass der von der WADA beim TAS angefochtene Entscheid betreffend Kürzung der Sperre auf 15 Monate von der FILA Federal Appeal Commission ausging. Damit war das TAS zur Beurteilung der Berufung der WADA zuständig.
Die Rüge der Beschwerdeführer, das TAS hätte seine Zuständigkeit zur Beurteilung der Berufung der WADA nicht bejahen dürfen, erweist sich als unbegründet.
6. Für den Fall, dass angenommen werde, dass der Entscheid betreffend Reduktion der Sperre von der FILA Federal Appeal Commission gefällt worden sei, rügen die Beschwerdeführer, dass das TAS im Sinne von <ref-law> über Streitpunkte entschieden habe, die ihm nicht unterbreitet worden seien. Denn auch wenn die FILA Federal Appeal Commission tatsächlich einen formellen Entscheid gefällt hätte, wäre noch nicht erstellt, dass es sich dabei um den Entscheid vom 20. Juni 2007 handle. Die Beschwerdegegnerin 1 habe vor dem TAS den Entscheid vom 20. Juni 2007 angefochten, der vom FILA Präsidenten gefällt worden sei. Falls das TAS im angefochtenen Schiedsentscheid einen Entscheid der FILA Federal Appeal Commission aufgehoben hätte, hätte es über einen Streitpunkt entschieden, der ihm nicht unterbreitet worden sei.
Unter <ref-law> fallen Schiedsentscheide, die mehr oder anderes zusprechen, als verlangt wurde oder die Rechtsbegehren unbeurteilt lassen (<ref-ruling> E. 3a). Diese Konstellation ist vorliegend nicht gegeben. Im Vorfeld der Berufung blieb für die WADA unklar, ob der Entscheid betreffend Reduktion der Sperre von der FILA Federal Appeal Commission oder vom FILA Präsidenten ausgegangen war. Sie focht daher den Entscheid vom 20. Juni 2007 an "irrespective of whether it had been taken by FILA Federal Appeal Commission or by the President". Es wird also nicht präzisiert, welches Organ der FILA den Entscheid gefällt hat. Entsprechend lautet Ziffer 4 des Schiedsentscheids lediglich: "The decision of FILA, dated 20 June 2007, is set aside." Bei dieser Sachlage kann nicht gesagt werden, das TAS habe der Beschwerdegegnerin 1 etwas anderes zugesprochen, als sie verlangt habe.
7. Die Beschwerdeführer bringen schliesslich vor, der angefochtene Schiedsentscheid verstosse gegen den formellen Ordre public (<ref-law>). Die unzutreffende Bejahung der Zuständigkeit des TAS führe dazu, dass die Beschwerdeführerin 1 von der staatlichen Gerichtsbarkeit ausgeschlossen sei. Im Bereich der Sportschiedsgerichtsbarkeit sei dies um so gravierender, als dort die Sportler keine andere Wahl hätten, als der Schiedsklausel der Weltsportverbände zuzustimmen. Der angefochtene Entscheid, zu dem das TAS gar nicht zuständig gewesen sei, stehe daher im Ergebnis in einem unerträglichen Widerspruch zum Rechtsempfinden.
Der Rüge kann von vornherein nicht gefolgt werden, weil es nicht zutrifft, dass das TAS zur Beurteilung der Berufung der Beschwerdegegnerin 1 nicht zuständig gewesen ist. Das TAS hat seine Zuständigkeit nicht zu Unrecht bejaht. Die Rüge, welche auf der gegenteiligen Annahme beruht, stösst daher ins Leere.
8. Die Beschwerde erweist sich als unbegründet und ist abzuweisen. Dem Ausgang des Verfahrens entsprechend werden die Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG). Eine Parteientschädigung ist nur an die Beschwerdegegnerin 1 auszurichten. Der ohnehin nicht anwaltlich vertretene Beschwerdegegner 2 liess sich nicht vernehmen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 4'000.-- werden den Beschwerdeführern auferlegt, unter solidarischer Haftbarkeit.
3. Die Beschwerdeführer haben die Beschwerdegegnerin 1 für das bundesgerichtliche Verfahren mit Fr. 5'000.-- zu entschädigen, unter solidarischer Haftbarkeit. Diese Entschädigung wird aus der an die Gerichtskasse bezahlten Sicherheitsleistung ausgerichtet.
4. Dieses Urteil wird den Parteien und dem Tribunal Arbitral du Sport (TAS) schriftlich mitgeteilt.
Lausanne, 17. März 2009
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Corboz
Der Gerichtsschreiber: Widmer