Sachverhalt: A. A.a X._, (Beschwerdeführer 1), geboren 1980, ist ein professioneller Fussballspieler brasilianischer Nationalität. Er spielt derzeit beim FC C._, auf Grundlage eines Ausleihvertrags dieses Clubs mit dem spanischen FC A._ (Beschwerdeführer 2). Der FC B._ (Beschwerdegegner 1) ist ein ukrainischer Fussballverein. Er ist Mitglied des ukrainischen Fussballverbands, der wiederum der Fédération Internationale de Football Association (FIFA; Beschwerdegegnerin 2) mit Sitz in Zürich angehört. Der Beschwerdeführer 2 ist Mitglied des spanischen Fussballverbands, der ebenfalls der FIFA angehört. A.b Während der Fussballsaison 2003/2004 spielte der Beschwerdeführer 1 für den italienischen FC D._. Am 20. Juni 2004 verpflichtete sich FC D._ zum Transfer des Spielers an den Beschwerdegegner 1 für einen Betrag von EUR 8 Mio. Am 26. Juni 2004 schloss der Beschwerdegegner 1 mit dem Beschwerdeführer 1 einen Arbeitsvertrag für die Zeit vom 1. Juli 2004 bis 1. Juli 2009 ab. Die Vereinbarung sah unter anderem Folgendes vor: "2.2. Transfer of the Football Player to another club or a squad prior to expiration of the contract is supposed only with the consent of the Club and under condition of compensation the Club's expenses on the keeping and training of the Football Player, cost of his rights, search of substitute and other costs in full measure. The size of indemnity is defined under the agreement between clubs. ... 3.3. During validity of the Contract, the Club undertakes: - to follow the condition of payment to the Football Player according to the present Contract; - to follow the condition of payment to the Football Player according to the present Contract; ... - in the case the Club receives a transfer offer in amount of 25,000,000 EUR or exceeding the some above the Club undertakes to arrange the transfer within the agreed period. ... - in the case the Club receives a transfer offer in amount of 25,000,000 EUR or exceeding the some above the Club undertakes to arrange the transfer within the agreed period. ... 4.1. Labor payment conditions of the Football Player are stipulated by the Parties in Appendix 1 to the present Contract. ... 4.1. Labor payment conditions of the Football Player are stipulated by the Parties in Appendix 1 to the present Contract. ... 6.3 Prior to the contract term expiration, it may be terminated only on such bases: - the agreement of the parties; - coming a court verdict into force by which the Football Player is sentenced to imprisonment; - under the initiative of the management of Club". Nachtrag 1 zum Arbeitsvertrag hält Folgendes fest: "Club pays to the Player as remuneration the following amounts, including taxes and other obligatory payments: 96,925.00 (ninety six thousand nine hundred twenty five) EUR [monthly]". A.c Am 1. Juni 2007 unterbreitete der italienische FC E._ dem Beschwerdegegner 1 ein Transferangebot für den Beschwerdeführer 1 über USD 7 Mio. Dieses wurde vom Beschwerdegegner 1 abgelehnt. A.d Am 2. Juli 2007 teilte der Beschwerdeführer 1 dem Beschwerdegegner 1 schriftlich mit, dass er seinen Arbeitsvertrag gemäss Art. 17 des FIFA-Reglements bezüglich Status und Transfer von Spielern ("Regulations for the Status and Transfer of Players"; nachfolgend: FIFA-Transferreglement) fristlos kündige. Er wies namentlich darauf hin, dass seine Kündigung innerhalb von fünfzehn Tagen nach dem letzten Saisonspiel in der Ukraine sowie am Ende der sogenannten Schutzzeit ("protected period") erfolgt sei. Dabei ist unbestritten, dass der Spieler den Arbeitsvertrag verfrüht und weder aus wichtigem Grund ("just cause") noch aus sportlich triftigen Gründen ("sporting just cause") auflöste. Mit Schreiben vom 5. Juli 2007 bestritt der Beschwerdegegner 1 die Zulässigkeit der erfolgten Kündigung und erinnerte den Beschwerdeführer 1 an seine arbeitsvertraglichen Pflichten. Am 19. Juli 2007 unterzeichnete der Beschwerdeführer 1 einen neuen Vertrag mit dem Beschwerdeführer 2 und verpflichtete sich für die nächsten drei Spielsaisons bis 30. Juni 2010 gegen ein Monatsgehalt von EUR 10'000.-- (zahlbar 14 Mal pro Jahr), einen Einstiegsbonus ("sign-on fee") von EUR 860'000.-- pro Saison sowie nicht weiter definierte Spielboni. Im Weiteren verpflichtete er sich für den Fall, dass er seinen Vertrag vorzeitig auflösen würde, zur Zahlung von EUR 6 Mio. A.e Mit Vereinbarung vom 17. Juli 2008 transferierte der Beschwerdeführer 2 den Spieler für die Spielsaison 2008/2009 vorübergehend an den FC C._. Der Vertrag enthält eine Optionsklausel zugunsten vom FC C._, die es diesem Club bis 15. Mai 2009 ermöglichen sollte, einseitig einen definitiven Transfer des Spielers zu bewirken. Für den Fall der Ausübung dieser Option ist eine Entschädigung von EUR 13 - 15 Mio. zuzüglich Mehrwertsteuer vorgesehen, je nachdem ob der FC C._ während der Saison 2008/2009 die UEFA Champions League erreichen sollte sowie abhängig von der Höhe der vom TAS zugesprochenen Entschädigung. Der Abschluss eines Arbeitsvertrags zwischen dem italienischen Club und dem Beschwerdeführer 1 wurde vorbehalten. Am 22. Juli 2008 schloss der Beschwerdeführer 1 für den Zeitraum bis 20. Juni 2011 einen Arbeitsvertrag mit dem FC C._ ab. Das feste Salär wurde auf EUR 895'000.-- für die Saison 2008/2009 sowie je EUR 3'220'900.-- für die Saisons 2009/2010 und 2010/2011 festgesetzt. Zusätzlich ist eine variable Entschädigung vorgesehen, auf deren Einzelheiten sich die Parteien zu verständigen haben. A.f Am 12. August 2008 schloss der Beschwerdeführer 1 mit dem Beschwerdeführer 2 einen Arbeitsvertrag mit einer festen Vertragsdauer bis 30. Juni 2011 ab, der die bestehende Vereinbarung vom 19. Juli 2007 ersetzte. Vorgesehen sind ein Gehalt von EUR 10'000.-- (zahlbar 14 Mal pro Jahr), ein Einstiegsbonus ("sign-on fee") von EUR 2.18 Mio. pro Saison sowie nicht weiter definierte Spielboni. Für den Fall der vorzeitigen Vertragsauflösung verpflichtet sich der Spieler zur Zahlung von EUR 22.5 Mio., wobei dieser Betrag vom Fussballclub einseitig und unter Erhöhung des Spielersalärs auf bis zu EUR 35 Mio. erhöht werden kann. B. B.a Am 25. Juli 2007 leitete der Beschwerdegegner 1 bei der Kammer zur Beilegung von Streitigkeiten ("Dispute Resolution Chamber") der FIFA ein Verfahren gegen die Beschwerdeführer ein mit dem Antrag, diese seien solidarisch zur Zahlung von EUR 25 Mio. zu verpflichten. Die Beschwerdeführer schlossen auf Abweisung dieses Begehrens und auf Festsetzung der Entschädigung auf EUR 3.2 Mio. Mit Entscheid vom 2. November 2007 sprach die Kammer zur Beilegung von Streitigkeiten dem Beschwerdegegner 1 gestützt auf Art. 17 des FIFA-Transferreglements einen Betrag von EUR 6.8 Mio. zu, zuzüglich Verzugszins zu 5 % nach Ablauf von 30 Tagen ab Entscheidfällung. Zur Begründung wurde ausgeführt, dem Beschwerdegegner 1 stehe eine Zahlung von EUR 2.4 Mio. unter dem Titel des Restwerts des Arbeitsvertrags ("remaining value of the player's employment contract") zu, nachdem der Beschwerdeführer 1 noch für zwei Jahre vertraglich gebunden gewesen wäre und sein Monatslohn ungefähr EUR 100'000.-- betrug. Indem der Spieler den Arbeitsvertrag zwei Jahre vor dem vorgesehenen Vertragsende aufgelöst habe, sei es dem Beschwerdegegner 1 verunmöglicht worden, die Vergütungen und Auslagen für den im Jahr 2004 erfolgten Transfer über den Zeitraum von fünf Jahren zu amortisieren. Die Transfersumme von EUR 8 Mio., die der Beschwerdegegner 1 an den vormaligen Club des Spielers bezahlte, sei zu zwei Fünfteln noch nicht amortisiert, weshalb dem Beschwerdegegner 1 ein zusätzlicher Anspruch über EUR 3.2 Mio. zustehe. Unter dem Titel "Besonderheit des Sports" ("specificity of sport") nach Art. 17 Abs. 1 des FIFA-Transferreglements seien dem Beschwerdegegner 1 weitere EUR 1.2 Mio. zuzusprechen, weil dem Spieler ein grober Verstoss gegen den Grundsatz von Treu und Glauben vorzuwerfen sei, indem er den Arbeitsvertrag absichtlich und ohne vorgängigen Hinweis verletzt habe, nachdem er kurz zuvor noch eine Erhöhung seines Salärs akzeptiert habe. B.b Sowohl die Beschwerdeführer als auch der Beschwerdegegner 1 legten gegen den Entscheid der Kammer zur Beilegung von Streitigkeiten vom 2. November 2007 Berufung ein. Mit Schiedsentscheid vom 19. Mai 2009 hob das Tribunal Arbitral du Sport (TAS) den Entscheid vom 2. November 2007 teilweise auf und verpflichtete die Beschwerdeführer solidarisch zur Zahlung von EUR 11'858'934.-- zuzüglich Zins zu 5 % seit dem 5. Juli 2007. C. Mit Beschwerde in Zivilsachen vom 18. Juni 2009 beantragen die Beschwerdeführer dem Bundesgericht, es sei der Schiedsentscheid des TAS vom 19. Mai 2009 aufzuheben. Im Weiteren sei festzustellen, dass der Beschwerdeführer 1 dem Beschwerdegegner 1 eine Entschädigung von EUR 2'363'760.--, eventualiter eine Entschädigung von EUR 3'200'000.-- schulde. Sodann sei festzustellen, dass der Beschwerdeführer 1 und der Beschwerdeführer 2 nicht solidarisch für die Entschädigung hafteten. Eventualiter sei die Sache zu neuer Entscheidung an das TAS zurückzuweisen. In verfahrensmässiger Hinsicht ersuchen sie unter anderem um Durchführung einer öffentlichen Parteiverhandlung. Der Beschwerdegegner 1 beantragt die Abweisung der Beschwerde, soweit auf diese einzutreten sei. Die Beschwerdegegnerin 2 sowie das TAS schliessen auf Abweisung der Beschwerde. Die Akten des Schiedsverfahrens wurden beigezogen. Mit Eingabe vom 21. Dezember 2009 nahmen die Beschwerdeführer in einer Replik Stellung zu den Beschwerdeantworten sowie der Vernehmlassung der Vorinstanz. Am 18. März 2010 reichten sie dem Bundesgericht in einer weiteren Eingabe einen am 16. März 2010 in einer Streitsache zwischen Drittparteien ergangenen Entscheid des Gerichtshofs der Europäischen Union (EuGH) ein. Der Beschwerdegegner 1 und die Beschwerdegegnerin 2 äusserten sich dazu mit Eingaben vom 1. April 2010. Die Beschwerdeführer nahmen dazu mit Eingabe vom 21. April 2010 wiederum Stellung, worauf der Beschwerdegegner 1 und die Beschwerdegegnerin 2 dem Bundesgericht ihrerseits am 3. bzw. 5. Mai 2010 ihre Entgegnungen einreichten. D. Mit Verfügung vom 8. September 2009 erteilte das Bundesgericht der Beschwerde aufschiebende Wirkung.