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.

Erwägungen:
1. Die Beschwerde in Zivilsachen ist gegen Entscheide von Schiedsgerichten unter den Voraussetzungen der Art. 190-192 IPRG zulässig (<ref-law>).
1.1 Der Sitz des Schiedsgerichts befindet sich vorliegend in Lausanne. Sowohl die Beschwerdeführer als auch der Beschwerdegegner 1 hatten im relevanten Zeitpunkt ihren Sitz bzw. Wohnsitz ausserhalb der Schweiz. 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).
1.2 Die Beschwerde in Zivilsachen im Sinne von <ref-law> ist grundsätzlich rein kassatorischer Natur, d.h. sie kann nur zur Aufhebung des angefochtenen Entscheids führen (vgl. <ref-law>, der die Anwendbarkeit von <ref-law> ausschliesst, soweit dieser dem Bundesgericht erlaubt, in der Sache selbst zu entscheiden). Eine Ausnahme davon gilt, wie schon im Rahmen der altrechtlichen staatsrechtlichen Beschwerde, soweit der Streit die Zuständigkeit des Schiedsgerichts betrifft (<ref-ruling> E. 1b S. 282; <ref-ruling> E. 4 S. 95 f.; Urteile 4A_428/2008 vom 31. März 2009 E. 2.4; 4A_224/2008 vom 10. Oktober 2008 E. 2.4).
Unzulässig sind demnach die von den Beschwerdeführern über die Aufhebung des angefochtenen Schiedsentscheids hinaus gestellten Anträge, es 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, und dass der Beschwerdeführer 2 nicht solidarisch für die Entschädigung hafte. Soweit die Beschwerdeführer vom Bundesgericht einen materiellen Entscheid begehren, ist auf die Anträge nicht einzutreten.
1.3 Zulässig sind allein die Rügen, die in <ref-law> abschliessend aufgezählt sind (<ref-ruling> E. 5 S. 187; <ref-ruling> E. 1a S. 53; <ref-ruling> E. 1a S. 282). Nach <ref-law> prüft das Bundesgericht nur die Rügen, die in der Beschwerde vorgebracht und begründet worden sind; dies entspricht der in <ref-law> für die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht vorgesehenen Rügepflicht (<ref-ruling> E. 5 S. 187 mit Hinweis). Appellatorische Kritik ist unzulässig (<ref-ruling> E. 3b S. 382).
1.4 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den das Schiedsgericht festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung des Schiedsgerichts weder berichtigen noch ergänzen, selbst wenn diese offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (vgl. <ref-law>, der die Anwendbarkeit von <ref-law> sowie <ref-law> 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 <ref-law> 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).
1.5 Die Parteien verkennen diese Grundsätze teilweise.
1.5.1 Sowohl die Beschwerdeführer als auch der Beschwerdegegner 1 legen in ihren Rechtsschriften den Ablauf der Ereignisse sowie des Verfahrens aus ihrer Sicht dar und weichen darin in verschiedenen Punkten von den tatsächlichen Feststellungen der Vorinstanz ab oder erweitern diese, ohne substantiiert Ausnahmen von der Sachverhaltsbindung geltend zu machen. Zudem bringen sie teilweise neue Tatsachen und Beweismittel vor. So tragen die Beschwerdeführer etwa vor, der Beschwerdeführer 1 werde nächste Saison beim Beschwerdeführer 2 spielen und reichen dazu eine Bestätigung des CEO des Beschwerdeführers 2 vom 16. Juni 2009 ein. Der Beschwerdegegner 1 schildert demgegenüber die tatsächlichen Entwicklungen im Nachgang des Vertragsabschlusses zwischen dem Beschwerdeführer 1 und dem FC C._ vom 17. Juli 2008 aus seiner Sicht und behauptet unter anderem unter Hinweis auf neu eingereichte Zeitungsartikel, die vereinbarte Option für eine Ablösesumme von EUR 13 - 15 Mio. sei vom FC C._ ausgeübt und der Spieler sei definitiv übernommen worden. Die Beschwerdeführer gehen zudem in unzulässiger Weise über den verbindlich festgestellten Sachverhalt des angefochtenen Entscheids hinaus, wenn sie sich vor Bundesgericht darauf berufen, die wirtschaftliche Lage erlaube es dem Beschwerdeführer 1 nicht, den auferlegten Betrag zu bezahlen. Ihre Vorbringen haben insoweit unbeachtet zu bleiben.
1.5.2 Die Beschwerdeführer üben teilweise appellatorische Kritik am angefochtenen Entscheid, so etwa mit den Vorbringen, der Beschwerdegegner 1 habe durch die Vertragsauflösung keinen Schaden erlitten, das TAS habe im Zusammenhang mit der Schadensberechnung eine unzutreffende Beweiswürdigung vorgenommen oder es habe Art. 17 Abs. 1 des FIFA-Transferreglements unrichtig ausgelegt. Damit, wie auch mit der Bestreitung der solidarischen Haftung des Beschwerdeführers 2, verfehlen sie die gesetzlichen Begründungsanforderungen im Rahmen einer Schiedsbeschwerde (vgl. <ref-law>).
1.5.3 Die Beschwerdeführer verlangen zu Unrecht unter Berufung auf Art. 6 und 13 EMRK, <ref-law> sowie <ref-law> eine Erweiterung der Überprüfungsbefugnis des Bundesgerichts. Sie übersehen dabei, dass die eingeschränkte Kognition nach <ref-law> in Verbindung mit <ref-law> für sämtliche Verfahren der internationalen Schiedsgerichtsbarkeit gilt.
Da mit einer Beschwerde gegen einen internationalen Schiedsentscheid nach <ref-law> ausschliesslich die in dieser Bestimmung abschliessend aufgezählten Beschwerdegründe angerufen werden können, nicht jedoch direkt eine Verletzung der Bundesverfassung, der EMRK oder weiterer Staatsverträge (vgl. Urteile 4A_612/2009 vom 10. Februar 2010 E. 2.4.1; 4P.105/2006 vom 4. August 2006 E. 7.3; 4P.64/2001 vom 11. Juni 2001 E. 2d/aa, nicht publ. in <ref-ruling> ff.), ist im Übrigen auf die verschiedentlich gerügte Verletzung entsprechender Bestimmungen grundsätzlich nicht einzutreten. Zwar können die aus der BV bzw. der EMRK fliessenden Grundsätze gegebenenfalls bei der Konkretisierung der nach <ref-law> anrufbaren Garantien herangezogen werden; angesichts der strengen Begründungsanforderungen (<ref-law>) ist jedoch in der Beschwerde eigens aufzuzeigen, inwiefern ein gesetzlich vorgesehener Beschwerdegrund gegeben sein soll.
2. Die Beschwerdeführer rügen zu Unrecht unter Berufung auf Art. 6 EMRK eine Verletzung des Anspruchs auf ein öffentliches Verfahren, da diese Bestimmung nach zutreffendem Verständnis der bundesgerichtlichen Rechtsprechung auf Verfahren der freiwilligen Schiedsgerichtsbarkeit nicht anwendbar ist. Entgegen der in der Beschwerde geäusserten Ansicht lässt sich daraus kein Anspruch auf eine öffentliche Parteiverhandlung im Rahmen des Schiedsverfahrens ableiten (Urteil 4A_612/2009 vom 10. Februar 2010 E. 4.1 mit Hinweisen).
Die Prüfungsbefugnis des Bundesgerichts im Rahmen der Schiedsbeschwerde ist nach <ref-law> erheblich eingeschränkt. Im vorliegenden Beschwerdeverfahren ist die Sache aufgrund der Akten spruchreif. Die Anordnung einer öffentlichen mündlichen Parteiverhandlung (<ref-law>), wie sie von den Beschwerdeführern verlangt wird, ist nicht angezeigt. Der Antrag auf Durchführung einer öffentlichen Parteiverhandlung vor Bundesgericht ist daher abzuweisen.
3. Die Beschwerdeführer werfen dem TAS im Zusammenhang mit dem anwendbaren Recht eine Verletzung des rechtlichen Gehörs (<ref-law>) vor.
3.1 Sie bringen vor, die Parteien hätten durch Unterstellung ihres Vertrags unter das FIFA-Transferreglement indirekt bestimmt, dass bei der Beurteilung der Entschädigung das nationale Recht am Sitz der beiden Vertragspartner zu berücksichtigen sei. Somit hätte das TAS das ukrainische und nur subsidiär das schweizerische Recht berücksichtigen müssen. Die Beschwerdeführer seien stets davon ausgegangen, dass das TAS gestützt auf das FIFA-Transferreglement das ukrainische Recht mitberücksichtigen würde. Das TAS habe diese Rechtsnormen, auf die das von den Parteien vereinbarte Transferreglement verweise, jedoch nicht angewendet, worin eine Verletzung des Grundsatzes pacta sunt servanda sowie von Art. 187 in Verbindung mit <ref-law> zu erblicken sei. Wende das Gericht "völlig neue (da selbst kreierte), von den Parteien in keiner Weise zu erwartende Rechtsnormen an", so die Beschwerdeführer, hätte ihnen zumindest das rechtliche Gehör gewährt werden müssen. Die Anwendung ukrainischen Rechts hätte nach Ansicht der Beschwerdeführer zu einem anderen Ergebnis geführt, da dieses keine Entschädigungspflicht gegenüber dem ehemaligen Fussballclub vorsehe, wenn der Spieler den Vertrag kündige, bevor er einen Vertrag mit einem neuen Club abschliesse.
Das TAS habe die vereinbarten Rechtsnormen nicht angewendet, sondern willkürlich "sportspezifische" eigene Regeln über Entschädigungszahlungen kreiert. Den Beschwerdeführern sei zu dieser "rechtswidrigen und überraschenden Rechtsanwendung" keine Gelegenheit zur Stellungnahme gegeben worden.
3.2 Die Beschwerdeführer zeigen mit ihren Vorbringen keine Verletzung des Grundsatzes des rechtlichen Gehörs (<ref-law>) auf. Sie kritisieren in unzulässiger Weise die Rechtsanwendung durch das TAS, ohne jedoch zu begründen, inwiefern es ihnen im Schiedsverfahren verunmöglicht worden sein soll, ihren Standpunkt hinsichtlich des anwendbaren Rechts darzulegen. Eine überraschende Rechtsanwendung, zu der die Beschwerdeführer eigens hätten angehört werden müssen, ist nicht erkennbar; im Gegenteil mussten die Parteien offensichtlich mit der Anwendung von Art. 17 des FIFA-Transferreglements rechnen, stützte doch bereits die Kammer zur Beilegung von Streitigkeiten der FIFA ihren Entscheid auf diese Bestimmung. Ebenso wenig trifft zu, dass die Beschwerdeführer zur Frage des anwendbaren Rechts keine Gelegenheit zur Stellungnahme erhalten hätten. Gemäss dem angefochtenen Entscheid haben sich die Beschwerdeführer im Schiedsverfahren nicht dazu geäussert, inwiefern ukrainisches Recht anwendbar sein und einen Einfluss auf die Berechnung der geschuldeten Entschädigung haben soll. Von einer Gehörsverletzung kann keine Rede sein.
Die Beschwerdeführer übersehen im Übrigen, dass die Verletzung von Art. 16 bzw. <ref-law> keinen nach <ref-law> vorgesehenen Rügegrund darstellt. Das TAS hat zudem den Grundsatz der Vertragstreue nicht verletzt, wenn es davon ausgegangen ist, dass bei der Bemessung der Entschädigung nach Art. 17 des FIFA-Transferreglements nationales Recht ("the law of the country concerned") zu berücksichtigen sei, es jedoch gleichzeitig erwogen hat, diesem Kriterium mangels entsprechender Vorbringen der Parteien keine Rechnung tragen zu können.
Soweit die Beschwerdeführer in diesem Zusammenhang auch eine Verletzung des Ordre public (<ref-law>) behaupten, verfehlen sie die gesetzlichen Begründungsanforderungen (vgl. <ref-law>). Abgesehen davon stiesse der Vorwurf einer Umgehung ausländischer Vorschriften mit Ordre public-Charakter auch deshalb ins Leere, weil die Beschwerdeführer im Schiedsverfahren keine entsprechenden Behauptungen erhoben, sondern im Gegenteil auf Argumente gestützt auf das ukrainische Recht überhaupt verzichteten.
Unverständlich ist der vor Bundesgericht erstmals erhobene Vorwurf, das TAS habe die Frage der Schiedsfähigkeit nicht geprüft; für die Beurteilung arbeitsrechtlicher Streitigkeiten seien nach ukrainischem Recht zwingend die ordentlichen Gerichte zuständig. Die Beschwerdeführer haben den Entscheid der Kammer zur Beilegung von Streitigkeiten der FIFA selber beim TAS angefochten. Die Berufung auf die fehlende Schiedsfähigkeit ist unter diesen Umständen unzulässig (vgl. Urteil 4A_370/2007 vom 21. Februar 2008 E. 5.2.2).
4. Die Beschwerdeführer rügen in verschiedener Hinsicht einen Verstoss gegen den Ordre public (<ref-law>).
4.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 (<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 Grundsätzen 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 S. 392 ff. mit Hinweisen).
4.2 Die Beschwerdeführer verkennen teilweise den Begriff des Ordre public sowie die für entsprechende Rügen geltenden strengen Begründungsanforderungen (vgl. <ref-ruling> E. 3 S. 606). Ihre Beschwerdeschrift enthält über weite Strecken allgemein gehaltene Ausführungen, denen sich keine hinreichend begründeten Rügen entnehmen lassen. Zudem erschöpfen sich ihre Darlegungen teilweise in appellatorischer Kritik am angefochtenen Entscheid, was im Rahmen des Beschwerdeverfahrens nicht zulässig ist (<ref-ruling> E. 3b S. 382).
Die Beschwerdeführer äussern sich etwa ausführlich zum Bosman-Urteil des EuGH vom 15. Dezember 1995 (C-415/93 Union royale belge des sociétés de football association gegen Jean-Marc Bosman, Slg. 1995 Seite I-04921) sowie zur Entstehungsgeschichte und Auslegung des FIFA-Transferreglements. Ausgehend davon unterbreiten sie dem Bundesgericht ihre Auffassung der nach Art. 17 des FIFA-Transferreglements zulässigen Kündigungsgründe sowie der zutreffenden Grundsätze der Schadensbemessung. Damit zeigen sie ebenso wenig einen Verstoss gegen den Ordre public (<ref-law>) auf wie mit der Behauptung, der Beschwerdegegner 1 habe durch die Vertragsauflösung keinen Schaden erlitten bzw. das TAS habe den Wert des Spielers willkürlich bestimmt. Appellatorisch ist zudem das Vorbringen, die Vorinstanz habe eine Transfersumme als massgeblich erachtet, die nie bezahlt worden sei, da der FC C._ die vorgesehene Option nicht ausgeübt habe sowie die Behauptung, das TAS berücksichtige die "Bruttoablösesumme" statt die "Nettoablösesumme".
Selbst wenn die Beschwerdeführer mit ihren nach Ablauf der Beschwerdefrist eingereichten Eingaben vom 18. März 2010 sowie 21. April 2010 gehört werden könnten, zeigen sie mit ihren Ausführungen zum Urteil des EuGH vom 16. März 2010 C-325/08 Olympique Lyonnais SASP gegen Olivier Bernard, Newcastle UFC keinen nach <ref-law> vorgesehenen Beschwerdegrund auf, sondern üben einmal mehr unzulässige Kritik an der Schadensberechnung des Schiedsgerichts. Sie behaupten dabei einen Verstoss "gegen Grundprinzipien des europäischen Wirtschaftsraums", legen jedoch weder dar, inwiefern eine Schadenersatzpflicht infolge vertragswidrigen Wechsels eines Fussballspielers von einem ukrainischen zu einem spanischen Fussballclub eine unzulässige Einschränkung der Arbeitnehmerfreizügigkeit innerhalb der Europäischen Union nach Art. 45 der konsolidierten Fassung des Vertrags über die Arbeitsweise der Europäischen Union vom 13. Dezember 2007 (AEUV; ABl. Nr. C 115 vom 9. Mai 2008, S. 47 ff.) darstellen soll, noch zeigen sie einen Zusammenhang mit dem Ordre public nach <ref-law> auf.
Überdies verkennen die Beschwerdeführer, dass sich mit dem verschiedentlich erhobenen Vorwurf der Verletzung wettbewerbsrechtlicher Vorschriften keine Ordre public-Widrigkeit begründen lässt (vgl. <ref-ruling> E. 3.2 S. 397 f.), weshalb ihre Argumente der unzulässigen Wiedereinführung eines wettbewerbswidrigen Transfersystems, der Verletzung der Wirtschaftsfreiheit sowie weiterer Wettbewerbsverstösse ins Leere stossen. Abgesehen davon ist entgegen der Ansicht der Beschwerdeführer nicht erkennbar, inwiefern die freie Berufswahl, der freie Zugang zu einer privatwirtschaftlichen Erwerbstätigkeit oder die Freizügigkeit des Arbeitnehmers in unzulässiger Weise eingeschränkt sein sollen, wenn der Arbeitnehmer bei ungerechtfertigter Auflösung seines Arbeitsverhältnisses zur Zahlung von Schadenersatz verpflichtet wird.
4.3 Die Beschwerdeführer bringen unter Hinweis auf den Ordre public (<ref-law>) vergeblich vor, der angefochtene Schiedsspruch leide hinsichtlich der Bemessung der Entschädigungssumme an einem unauflöslichen Widerspruch. Ein innerer Widerspruch in der Begründung eines Entscheids stellt entgegen der in der Beschwerde geäusserten Ansicht keine Verletzung des Ordre public dar (Urteile 4A_612/2009 vom 10. Februar 2010 E. 6.2.2; 4A_464/2009 vom 15. Februar 2010 E. 5.1).
4.4 Der unter Berufung auf <ref-law> erhobene Vorwurf der übermässigen Bindung des Spielers überzeugt nicht.
Die Verletzung dieser Bestimmung bedeutet nicht ohne Weiteres einen Verstoss gegen den Ordre public; vielmehr ist ein solcher nur im Falle einer offensichtlichen und schwerwiegenden Grundrechtsverletzung denkbar (vgl. Urteile 4A_458/2009 vom 10. Juni 2010 E. 4.4.3.2; 4P.12/2000 vom 14. Juni 2000 E. 5b/aa mit Hinweisen). Dabei ist zu beachten, dass eine vertragliche Beschränkung der wirtschaftlichen Freiheit nur dann als übermässig im Sinne von <ref-law> betrachtet wird, wenn sie den Verpflichteten der Willkür eines anderen ausliefert, seine wirtschaftliche Freiheit aufhebt oder in einem Masse einschränkt, dass die Grundlagen seiner wirtschaftlichen Existenz gefährdet sind (<ref-ruling> E. 5 S. 345 f. mit Hinweisen).
Eine derartige vertragliche Beschränkung liegt im zu beurteilenden Fall nicht vor. Der Beschwerdeführer 1 hat sich gegen ein hohes Salär für eine Dauer von fünf Jahren zur Arbeitsleistung im Dienste des Beschwerdegegners 1 verpflichtet. Wie in der Beschwerdeantwort zu Recht eingewendet wird, ist eine solche mehrjährige Bindung unter dem Gesichtswinkel des Persönlichkeitsschutzes nicht unzulässig. Eine übermässige Bindung lässt sich auch nicht damit begründen, dass der Beschwerdeführer 1 infolge Vertragsverletzung für den eingetretenen Schaden aufzukommen hat, entspricht eine solche Sanktion doch anerkannten Grundsätzen vertraglicher Haftung.
4.5 Unbegründet ist auch die Rüge, das TAS habe durch Zusprache von sogenannten Punitive Damages, die mit einer angemessenen Entschädigung des Verletzten nichts mehr zu tun hätten, gegen den Ordre public verstossen.
Dem angefochtenen Schiedsentscheid lässt sich entgegen der Behauptung der Beschwerdeführer nicht entnehmen, dass das TAS eine Verdoppelung des Schadenersatzes vorgenommen hätte. Insbesondere hat es nicht eine "fiktive Leistung" des Spielers während der zweijährigen Restlaufzeit des Vertrags entschädigt und zusätzlich den Gegenwert der Ablösesumme zugesprochen, wie dies in der Beschwerde vorgebracht wird, sondern die Transfersumme bei der Beurteilung des Werts der entgangenen Dienstleistung mitberücksichtigt. Die Rüge stösst bereits aus diesem Grund ins Leere.
Fehl geht auch der Vorwurf, einschlägig sei entgegen dem angefochtenen Entscheid nicht <ref-law>, sondern <ref-law>; die zusätzliche Entschädigung von EUR 600'000.--, entsprechend sechs Monatslöhnen, die das TAS dem Beschwerdegegner 1 zugesprochen hat, weil der Beschwerdeführer 1 seine Arbeitsstelle nur wenige Wochen vor Beginn der Qualifikationsrunden der UEFA Champions League verliess, sei im Schweizer Recht nicht vorgesehen und daher rechtswidrig. Damit lässt sich ebenso wenig eine Ordre public-Widrigkeit begründen wie mit dem Vorbringen, nach Art. 130 des ukrainischen Arbeitsrechts hafte ein Arbeitnehmer dem Arbeitgeber nur für Schäden, die der Arbeitgeber infolge unerlaubter Handlungen erlitten habe.
Mit den Vorbringen, die zugesprochene Entschädigung entspreche nicht dem konkreten Schaden, den der Beschwerdegegner 1 allenfalls erlitten habe und sei übermässig bzw. deren Berechnung sei widersprüchlich, kritisieren die Beschwerdeführer einmal mehr in appellatorischer Weise die vorinstanzliche Schadensberechnung. Entsprechendes gilt für den Einwand, das TAS habe verschiedene Grundprinzipien des Schadenersatzrechts missachtet. Die Beschwerdeführer verlangen mit ihren Ausführungen eine materielle Überprüfung des angefochtenen Schiedsentscheids, ohne jedoch eines Missachtung eines dem Ordre public (<ref-law>) zugehörenden fundamentalen Rechtsgrundsatzes aufzuzeigen.
4.6 Unbegründet ist auch der Einwand der Beschwerdeführer, die Art und Weise, wie das TAS die Entschädigung bestimme, führe zu einer Ungleichbehandlung von Arbeitnehmer und Arbeitgeber; dadurch werde mit der Kündigungsparität ein wichtiges Grundprinzip des Schweizer Arbeitsrechts bzw. die arbeitnehmerfreundliche Kündigungsmöglichkeit nach ukrainischem Arbeitsrecht verletzt. Abgesehen davon, dass eine verpönte Ungleichbehandlung der Parteien hinsichtlich der Kündigungsmöglichkeiten nicht ersichtlich ist, legen die Beschwerdeführer nicht dar, inwiefern der Grundsatz der Kündigungsparität zum Ordre public zählen soll.
4.7 Da im vorliegenden Schiedsverfahren die Zusprechung von Schadenersatz infolge (unbestrittener) Verletzung eines Arbeitsvertrags und nicht eine Vereinsstrafe oder sonstige Strafe zu beurteilen war, wie dies die Beschwerdeführer behaupten, braucht auf ihre Ausführungen unter dem Titel "Nulla Poena sine Lege" nicht weiter eingegangen zu werden.
5. Die Beschwerde erweist sich als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend werden die Beschwerdeführer unter solidarischer Haftbarkeit kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und 5 sowie Art. 68 Abs. 2 und 4 BGG).

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