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.