Sachverhalt:
A. X._ und Y._, beide mit Wohnsitz in Buenos Aires/Argentinien, (Beschwerdeführer) sind als Spielervermittler tätig. Mit Vertrag vom 30. Juni 2003 wurden die beiden Beschwerdeführer vom Club B._, einem argentinischen Fussballverein beauftragt, den Transfer des Fussballspielers Z._ zum Fussballclub A._ (Beschwerdegegner) auszuhandeln und abzuwickeln.
Der Vertrag sah vor, dass die Beschwerdeführer den Fussballverein B._ exklusiv bis zum 30. August 2003 vertreten durften. Im Gegenzug verpflichtete sich B._, den Beschwerdeführern 10 % der Transfersumme als Vergütung zu entrichten. Für den Fall der Nichterfüllung seitens B._ wurde der doppelte Betrag (d.h. 20 % der Transfersumme) als Konventionalstrafe vereinbart.
Am 8. Juli 2003 schlossen B._, der Beschwerdegegner sowie eine Gesellschaft, die an den Transferrechten des Spielers beteiligt war, einen Vertrag über den Transfer von Z._ von B._ zum Beschwerdegegner gegen eine Transfersumme von EUR 3'500'000.-- ab (nachfolgend Transfervertrag). Der Transfervertrag wurde unter der aufschiebenden Bedingung abgeschlossen, dass Z._ nach erfolgreicher medizinischer Untersuchung einen Arbeitsvertrag mit dem Beschwerdegegner abschliesse.
Anlässlich der medizinischen Untersuchung vom 21. Juli 2003 erachteten die Ärzte des Beschwerdegegners die körperliche Verfassung des Spielers für unzureichend. Entsprechend erklärte der Beschwerdegegner die aufschiebende Bedingung als nicht erfüllt und verzichtete auf die Unterzeichnung des Arbeitsvertrags mit dem Spieler. Einige Tage später kam es zu einem Transfer von Z._ zu einem anderen Fussballclub.
B. In der Folge machten die Beschwerdeführer vor der Fédération Internationale de Football Association (FIFA) gestützt auf die FIFA-Bestimmungen sowie Art. 41 OR eine Schadenersatzforderung über EUR 700'000.-- gegen den Beschwerdegegner geltend. Der zuständige Einzelrichter wies die Klage ab.
Diesen Entscheid bestätigte das Tribunal Arbitral du Sport (TAS) mit Schiedsurteil vom 29. Februar 2008 auf Appellation der Beschwerdeführer hin.
C. Mit Beschwerde in Zivilsachen beantragen die Beschwerdeführer dem Bundesgericht, das Urteil des TAS vom 29. Februar 2008 sei aufzuheben. Zudem sei der Beschwerdegegner zu einer Entschädigung von EUR 700'000.-- plus Zins zu 5 % seit dem 8. Juli 2003 zu verurteilen. Schliesslich beantragen die Beschwerdeführer die Edition verschiedener Dokumente bzw. Aufzeichnungen.
Der Beschwerdegegner sowie das TAS schliessen auf Abweisung der Beschwerde, soweit überhaupt darauf einzutreten sei.
D. Mit Verfügung vom 24. Juni 2008 wurde das Sicherstellungsbegehren des Beschwerdegegners abgewiesen.

Erwägungen:
1. 1.1 Nach Art. 54 Abs. 1 BGG ergeht der Entscheid des Bundesgerichts in einer Amtssprache, in der Regel derjenigen des angefochtenen Entscheids. Wurde dieser Entscheid in einer anderen Sprache abgefasst, bedient sich das Bundesgericht der von den Parteien verwendeten Amtssprache.
Der angefochtene Entscheid ist in spanischer Sprache abgefasst. Da es sich dabei nicht um eine Amtssprache handelt und sich die Parteien vor Bundesgericht verschiedener Sprachen bedienen, ergeht der Entscheid des Bundesgerichts praxisgemäss in der Sprache der Beschwerde (Urteil 4A_506/2007 vom 9. September 2008, E. 1).
1.2 Auf die Übersetzung einer von einer Partei eingereichten und nicht in einer Amtssprache abgefassten Urkunde kann mit dem Einverständnis der anderen Partei verzichtet werden (Art. 54 Abs. 3 BGG). Da sich der Beschwerdegegner hat vernehmen lassen, ohne eine Übersetzung des angefochtenen Entscheids zu verlangen, ist von einem Verzicht auf die Übersetzung auszugehen.
2. 2.1 Die Beschwerdeführer bringen selbst vor, das TAS sei ein internationales Schiedsgericht, dessen Entscheide nur unter den Voraussetzungen von Art. 190 Abs. 2 IPRG und Art. 77 BGG angefochten werden können. Zulässig sind allein die Rügen, die in Art. 190 Abs. 2 IPRG abschliessend aufgezählt sind (<ref-ruling> E. 5; <ref-ruling> E. 1a S. 53; <ref-ruling> E. 1a S. 282). Nach Art. 77 Abs. 3 BGG prüft das Bundesgericht nur die Rügen, die in der Beschwerde vorgebracht und begründet worden sind; dies entspricht der in Art. 106 Abs. 2 BGG für die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht vorgesehenen Rügepflicht (<ref-ruling> E. 5 mit Hinweis). Bei Rügen nach Art. 190 Abs. 2 lit. e IPRG ist die Unvereinbarkeit des angefochtenen Schiedsentscheids mit dem Ordre public im Einzelnen aufzuzeigen (<ref-ruling> E. 3 S. 606). Appellatorische Kritik ist unzulässig (<ref-ruling> E. 3b).
2.2 Die Beschwerde gegen internationale Schiedsgerichtsurteile ist rein kassatorischer Natur (Art. 77 Abs. 2 BGG, der die Anwendbarkeit von Art. 107 Abs. 2 BGG ausschliesst, soweit dieser dem Bundesgericht erlaubt, in der Sache selbst zu entscheiden). Dies verkennen die Beschwerdeführer, wenn sie dem Bundesgericht die Gutheissung ihrer Klage beantragen und sich dazu zu Unrecht auf eine volle Kognition des Bundesgerichts berufen. Die Beschwerdeführer selbst haben mit ihrer Appellation den Gang an das TAS gewählt und dessen Zuständigkeit auch vor Bundesgericht nicht in Frage gestellt (vgl. Art. 190 Abs. 2 lit. b IPRG). Entsprechend haben sie hinzunehmen, dass der ergangene Schiedsentscheid nur in beschränktem Rahmen (Art. 77 BGG in Verbindung mit Art. 190 IPRG) angefochten werden kann.
2.3 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den das Schiedsgericht festgestellt hat (Art. 105 Abs. 1 BGG). Es kann die Sachverhaltsfeststellung des Schiedsgerichts weder berichtigen noch ergänzen, selbst wenn diese offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht (vgl. Art. 77 Abs. 2 BGG, der die Anwendbarkeit von Art. 105 Abs. 2 sowie Art. 97 BGG ausschliesst). Allerdings kann das Bundesgericht die tatsächlichen Feststellungen des angefochtenen Schiedsentscheids überprüfen, wenn gegenüber diesen Sachverhaltsfeststellungen zulässige Rügen im Sinne von Art. 190 Abs. 2 IPRG vorgebracht oder ausnahmsweise Noven berücksichtigt werden (<ref-ruling> E. 5 S. 141; <ref-ruling> E. 5.2.2 S. 733, je mit Hinweisen). Wer sich auf eine Ausnahme von der Bindung des Bundesgerichts an die tatsächlichen Feststellungen der Vorinstanz beruft und den Sachverhalt gestützt darauf berichtigt oder ergänzt wissen will, hat mit Aktenhinweisen darzulegen, dass entsprechende Sachbehauptungen bereits im vorinstanzlichen Verfahren prozesskonform aufgestellt worden sind (vgl. <ref-ruling> E. 2a S. 486; <ref-ruling> E. 1c S. 473, je mit Hinweisen).
3. Die Beschwerdeführer rügen zunächst gestützt auf Art. 190 Abs. 2 lit. a IPRG die vorschriftswidrige Zusammensetzung des TAS, das den angefochtenen Entscheid gefällt hat.
3.1 Die Beschwerdeführer bringen zur Begründung ihrer Rüge vor, der Beschwerdegegner sei schon im Verfahren vor dem TAS von Rechtsanwalt Ibarrola vertreten gewesen. Dieser sei zwischen 2003 und Juni 2007 als hochrangiger Funktionär beim TAS angestellt gewesen und habe gemäss eigenen Angaben mehr als 400 Fälle geführt. Während seiner Tätigkeit beim TAS sei er bei jeder Audienz als Gerichtsschreiber tätig gewesen und habe an unzähligen Weiterbildungen teilgenommen, in denen die Schiedsrichter als Referenten aufgetreten seien und sei deshalb in ständigem Kontakt mit jedem einzelnen der TAS-Schiedsrichter gewesen. Seine langjährige Tätigkeit beim TAS habe zu einem weit über den normalen beruflichen Kontakt hinausgehenden Bezug zu den TAS-Schiedsrichtern geführt. Insbesondere habe der Rechtsvertreter des Beschwerdegegners, so die Beschwerdeführer weiter, einen starken persönlichen Bezug zu den Schiedsrichtern, zumal er vor und nach den Verhandlungen stets mit ihnen in kollegialer Weise den Fall besprochen habe. Dieser Umstand habe zu einer Befangenheit der am Schiedsverfahren beteiligten Schiedsrichter geführt, was der damalige Rechtsvertreter der Beschwerdeführer zu Beginn der mündlichen Verhandlung gerügt habe; die Rüge sei jedoch von den Schiedsrichtern überhört und die Verhandlung fortgesetzt worden.
3.2 Mit ihrer Behauptung, sie hätten die beteiligten Schiedsrichter wegen Befangenheit zu Beginn der mündlichen Verhandlung abgelehnt, weichen die Beschwerdeführer vom verbindlich festgestellten Sachverhalt des angefochtenen Entscheids ab (Art. 105 Abs. 1 BGG). Die Vorinstanz hielt nämlich hinsichtlich des Verfahrensverlaufs fest, dass keine der Parteien verfahrensrechtliche Einwendungen erhoben hätten. Soweit die Beschwerdeführer bezüglich dieser Sachverhaltsfeststellung sinngemäss eine Verletzung ihres rechtlichen Gehörs vorbringen (vgl. Art. 190 Abs. 2 lit. d IPRG), indem sie geltend machen, sie seien mit ihrer entsprechenden Rüge nicht gehört worden, so verfehlen sie die Begründungsanforderungen an eine gehörige Sachverhaltsrüge, da sie nicht mit Aktenhinweisen darlegen, dass sie entsprechende Tatsachenbehauptungen bereits vor der Vorinstanz prozesskonform vorgebracht haben. Darauf ist nicht einzutreten.
3.3 Fehlt es einem Schiedsgericht an Unabhängigkeit oder Unparteilichkeit, ist es als vorschriftswidrig zusammengesetzt im Sinne von Art. 190 Abs. 2 lit. a IPRG zu betrachten (<ref-ruling> E. 3.1 S. 449). Die Partei, die einen Schiedsrichter ablehnen will, hat den Grund der Ablehnung geltend zu machen, sobald sie von diesem Kenntnis erhält. Dieser Grundsatz, der in R34 des Code de l'arbitrage en matière de sport ausdrücklich festgehalten ist, bezieht sich sowohl auf Ablehnungsgründe, die der Partei tatsächlich bekannt waren als auch auf solche, von denen sie bei gehöriger Aufmerksamkeit hätte Kenntnis erlangen können (<ref-ruling> E. 4.2.2.1 S. 465 mit Hinweisen). Nach dem Grundsatz von Treu und Glauben verwirkt eine Partei ihren Anspruch auf Anrufung des Ablehnungsgrunds, wenn sie ihn nicht unverzüglich geltend macht; es geht nicht an, dass sie Ablehnungsgründe gleichsam in "Reserve" hält, um diese bei ungünstigem Prozessverlauf und voraussehbarem Prozessverlust nachzuschieben (<ref-ruling> E. 3.1 S. 449 mit Hinweisen).
Vorliegend machen die Beschwerdeführer nicht geltend, sie hätten von den behaupteten Ablehnungsgründen nicht schon zu Beginn des Schiedsverfahrens Kenntnis erhalten bzw. erhalten können. Vielmehr berufen sie sich - wenn auch ohne die Anforderungen an eine gehörige Sachverhaltsrüge zu erfüllen - darauf, bereits zu Beginn der mündlichen Verhandlung den Ausstand der Schiedsrichter verlangt zu haben und geben damit zu, dass ihnen die Tatsachen, die sie nun vor Bundesgericht zur Rüge der vorschriftswidrigen Zusammensetzung des TAS veranlassen, bereits damals bekannt gewesen waren. Da eine Ablehnung der Schiedsrichter gemäss den für das Bundesgericht verbindlichen Feststellungen der Vorinstanz (Art. 105 Abs. 1 BGG) vor dem Schiedsgericht jedoch nicht prozesskonform verlangt wurde, und dessen vorschriftswidrige Zusammensetzung (Art. 190 Abs. 2 lit. a IPRG) erstmals vor Bundesgericht gerügt wird, sind die Beschwerdeführer mit diesem Einwand ausgeschlossen. Unabhängig davon, ob ihre Vorbringen überhaupt geeignet wären, eine Ablehnung der Schiedsrichter zu begründen, was vorliegend fraglich ist, stösst die Rüge der Verletzung von Art. 190 Abs. 2 lit. a IPRG daher ins Leere. Die Beschwerdeführer rügen in zweifacher Hinsicht eine Verletzung ihres Gehörsanspruchs (Art. 190 Abs. 2 lit. d IPRG).
4. Nach Art. 190 Abs. 2 lit. d IPRG kann der Schiedsentscheid unter anderem angefochten werden, wenn der Anspruch auf rechtliches Gehör (Art. 182 Abs. 3 IPRG) verletzt wurde. Dieser entspricht - mit Ausnahme des Anspruchs auf Begründung - dem in Art. 29 Abs. 2 BV gewährleisteten Verfassungsrecht (<ref-ruling> E. 5 S. 37 f.; <ref-ruling> E. 2c). Die Rechtsprechung leitet daraus insbesondere das Recht der Parteien ab, sich zu allen für das Urteil wesentlichen Tatsachen zu äussern, ihren Rechtsstandpunkt zu vertreten, ihre entscheidwesentlichen Sachvorbringen mit tauglichen sowie rechtzeitig und formrichtig offerierten Mitteln zu beweisen, sich an den Verhandlungen zu beteiligen und in die Akten Einsicht zu nehmen (<ref-ruling> E. 6.1 S. 143; <ref-ruling> E. 5 S. 38; <ref-ruling> E. 2c). Aus dem Anspruch auf rechtliches Gehör folgt die grundsätzliche Pflicht der Behörde, die rechtserheblichen Vorbringen zu prüfen und zu würdigen. Dabei kann sie sich auf die für den Entscheid wesentlichen Gesichtspunkte beschränken (<ref-ruling> E. 2b S. 102 f.; <ref-ruling> E. 3b).
4.1 Die Beschwerdeführer machen zunächst geltend, das TAS habe die Aussage von Herrn W._, dem Präsidenten von B._, nur zu einem kleinen Teil verwendet sowie willkürlich und verzerrt wiedergegeben. Dies habe später dazu geführt, dass das TAS verschiedene Behauptungen der Beschwerdeführer als nicht bewiesen erachtet habe. Aus den Aussagen des Zeugen gehe klar hervor, dass ohne Zutun der Beschwerdeführer der Transfervertrag nie zustande gekommen wäre. Trotz dieser Aussage habe das TAS den Honoraranspruch der Beschwerdeführer in Frage gestellt und ihre Beteiligung am Transfervertrag als nicht bewiesen erachtet. Die Beschwerdeführer behaupten sodann, die Zustimmung des Spielers zum Transfer und das Zustandekommen eines (mündlichen) Arbeitsvertrags mit dem Beschwerdegegner sei mit der Aussage des Zeugen W._ bewiesen. Schliesslich seien die Aussagen des Zeugen, wonach sich der Spieler Z._ anlässlich der medizinischen Untersuchung in perfekter gesundheitlicher Verfassung befunden habe bzw. Sowohl B._ als auch der Spieler Z._ den Entscheid des Beschwerdegegners ablehnten, vom Schiedsgericht nicht berücksichtigt worden. Die Beschwerdeführer folgern aus den von ihnen erwähnten Aussagen, dass diese "bei richtiger Würdigung zu einem anderen Ausgang des Verfahrens" geführt hätten.
4.1.1 Nach der Rechtsprechung des Bundesgerichts reicht eine offensichtlich falsche oder aktenwidrige Feststellung für sich allein nicht aus, um einen internationalen Schiedsentscheid aufzuheben. Der Anspruch auf rechtliches Gehör enthält keinen Anspruch auf einen materiell richtigen Entscheid. Daher ist es nicht Sache des Bundesgerichts zu überprüfen, ob das Schiedsgericht sämtliche Aktenstellen berücksichtigt und richtig verstanden hat. Erforderlich ist eine formelle Rechtsverweigerung in dem Sinne, dass das rechtliche Gehör der Partei durch das offensichtliche Versehen faktisch ausgehöhlt wurde und die Partei im Ergebnis nicht besser dasteht, als wenn ihr das rechtliche Gehör zu einer entscheidwesentlichen Frage überhaupt nicht gewährt worden wäre. Wer aus einem offensichtlichen Versehen eine Verletzung des rechtlichen Gehörs ableiten will, hat demnach aufzuzeigen, dass ihm das richterliche Versehen verunmöglichte, seinen Standpunkt in Bezug auf ein prozessrelevantes Thema in den Prozess einzubringen und zu beweisen (<ref-ruling> E. 5.2; <ref-ruling> E. 2b-f).
4.1.2 Dies ist den Beschwerdeführern vorliegend nicht gelungen. Vielmehr beschränken sie sich darauf - im Übrigen ohne jegliche Aktenhinweise - verschiedenste Aussagen des Zeugen W._ zu erwähnen, die das Schiedsgericht übersehen bzw. unzutreffend gewürdigt haben soll und die ihrer Ansicht nach die Beweiswürdigung zu ihrem Nachteil beeinflusst haben. Damit unterziehen sie in Tat und Wahrheit die Beweiswürdigung des Schiedsgerichts einer appellatorischen Kritik. Sie legen einfach ihren eigenen Standpunkt dar und behaupten, er sei durch die Zeugenaussage erstellt. Dies ist im Rahmen der Schiedsbeschwerde nicht zulässig.
4.2 Auch mit ihren Ausführungen unter dem Titel "Verletzung des rechtlichen Gehörs der Beschwerdeführer bei der Beurteilung des Vorliegens einer unerlaubten Handlung durch den Beschwerdegegner" legen die Beschwerdeführer lediglich in appellatorischer Weise ihren Standpunkt dar und ziehen die materielle Richtigkeit des Schiedsspruchs in Zweifel, begründen aber keine formelle Rechtsverweigerung. So machen sie eine Verletzung von Art. 30 des FIFA-Reglements sowie der Beweislastregel (Art. 8 ZGB) geltend und zeigen auf, weshalb ihrer Ansicht nach die Voraussetzungen von Art. 41 OR erfüllt seien. Damit ist keine Verletzung des rechtlichen Gehörs dargetan.
5. Die Beschwerdeführer rügen schliesslich eine Verletzung des Ordre public nach Art. 190 Abs. 2 lit. e IPRG.
5.1 Die materiellrechtliche Überprüfung eines internationalen Schiedsentscheids durch das Bundesgericht ist auf die Frage beschränkt, ob der Schiedsspruch mit dem Ordre public vereinbar ist (BGE <ref-ruling> E. 3a S. 333). Gegen den Ordre public verstösst die materielle Beurteilung eines streitigen Anspruchs nur, wenn sie fundamentale Rechtsgrundsätze verkennt und daher mit der wesentlichen, weitgehend anerkannten Wertordnung schlechthin unvereinbar ist, die nach in der Schweiz herrschender Auffassung Grundlage jeder Rechtsordnung bilden sollte. Zu diesen Prinzipien gehören die Vertragstreue (pacta sunt servanda), das Rechtsmissbrauchsverbot, der Grundsatz von Treu und Glauben, das Verbot der entschädigungslosen Enteignung, das Diskriminierungsverbot und der Schutz von Handlungsunfähigen. Zur Aufhebung des angefochtenen Schiedsentscheids kommt es nur, wenn dieser nicht nur in der Begründung, sondern auch im Ergebnis dem Ordre public widerspricht (<ref-ruling> E. 2.2; <ref-ruling> E. 6b; <ref-ruling> E. 6a S. 166 f.).
5.2 Die Beschwerdeführer erblicken eine Verletzung des Grundsatzes der Vertragstreue sowie des Rechtsmissbrauchsverbots darin, dass das TAS zwar von einem gültig geschlossenen Transfervertrag zwischen B._ und dem Beschwerdegegner ausgehe, jedoch dem Beschwerdegegner das Recht einräume, ohne Grundangabe die Nichterfüllung der Suspensivbedingung herbeizuführen.
Die Rüge ist unbegründet. Der Grundsatz pacta sunt servanda ist nur dann verletzt, wenn das Schiedsgericht zwar die Existenz eines Vertrags bejaht, die daraus sich ergebenden Konsequenzen jedoch missachtet, oder - umgekehrt - die Existenz eines Vertrags verneint, jedoch trotzdem eine vertragliche Verpflichtung bejaht (BGE <ref-ruling> E. 6c S. 171; <ref-ruling> E. 4b S. 638; Urteil 4A_370/2007 vom 21. Februar 2008, E. 5.5). Wird ein Vertrag unter einer Suspensivbedingung abgeschlossen, so verletzt das Gericht den Grundsatz der Vertragstreue nicht, wenn es den Vertrag bei Ausbleiben der Bedingung als nicht verbindlich erachtet. Das TAS hat den Transfervertrag anders interpretiert respektive den festgestellten Sachverhalt rechtlich anders beurteilt, als dies die Beschwerdeführer tun. Darin liegt weder eine Verletzung des Grundsatzes pacta sunt servanda noch des Rechtsmissbrauchsverbots. Denn mit einer Rüge nach Art. 190 Abs. 2 lit. e IPRG kann nicht geltend gemacht werden, das Schiedsgericht habe nicht die zutreffende Vertragsbestimmung angewendet, sie falsch ausgelegt oder falsch angewendet (BGE <ref-ruling> E. 6c/cc in fine S. 171; <ref-ruling> E. 4b S. 638).
5.3 Soweit die Beschwerdeführer schliesslich eine Verletzung des Ordre public in Form eines Verstosses gegen den Grundsatz von Treu und Glauben behaupten und dazu vorbringen, der Beschwerdegegner habe andere - am vorliegenden Verfahren nicht beteiligte - Spieler trotz Verletzungen verpflichtet, sind ihre Vorbringen ungenügend begründet und gehen in unzulässiger Weise über den vorinstanzlich verbindlich festgestellten Sachverhalt (Art. 105 Abs. 1 BGG) hinaus. Darauf ist nicht einzutreten.
6. Die Beschwerde erweist sich als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend werden die Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 15'000.-- werden den Beschwerdeführern unter solidarischer Haftung und intern je zur Hälfte auferlegt.
3. Die Beschwerdeführer haben den Beschwerdegegner für das bundesgerichtliche Verfahren unter solidarischer Haftung und intern je zur Hälfte mit Fr. 17'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Tribunal Arbitral du Sport (TAS) schriftlich mitgeteilt.
Lausanne, 23. September 2008
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Corboz Leemann