Sachverhalt:
A. A.a X._ (Beschwerdeführer) ist ein deutscher Verein mit Sitz in D._, der dem Deutschen Fussball-Bund angehört.
Y._ (Beschwerdegegner) ist der nationale Fussballverband von F._ und gehört der Fédération Internationale de Football Association (FIFA) an.
A.b Am 7. Juli 2008 teilte der Beschwerdegegner dem Deutschen Fussball-Bund mit, dass unter anderem der Spieler Z._ "Z._" (nachfolgend Z._), der damals beim Beschwerdeführer spielte und weniger als 23 Jahre alt war, von der Nationalmannschaft von F._ zur Teilnahme an den Olympischen Spielen in Peking im August 2008 selektioniert worden sei. Der Beschwerdegegner bat den deutschen Nationalverband, den Beschwerdeführer anzuweisen, den Spieler für diesen Anlass freizustellen.
Mit Schreiben vom 11. Juli 2008 lehnte der Beschwerdeführer dieses Ersuchen ab und stellte sich auf den Standpunkt, dass nach dem anwendbaren FIFA-Reglement keine Verpflichtung für die Freigabe von Z._ bestehe.
Ebenfalls am 11. Juli 2008 ersuchte der Beschwerdegegner den Deutschen Fussball-Bund erneut, den Beschwerdeführer über seine Verpflichtung zur Freigabe des Spielers zu informieren. Der Deutsche Fussball-Bund antwortete am 17. Juli 2008, wobei er sich der Rechtsauffassung des Beschwerdeführers anschloss und eine Verpflichtung zur Freigabe verneinte. Am gleichen Tag teilte der Beschwerdegegner dem Beschwerdeführer den Flugplan des Spielers im Hinblick auf die Zusammenkunft der F._ Nationalmannschaft für die Olympischen Spiele mit.
Nachdem Z._ nicht ins Trainingslager eingerückt war, wies der Rechtsvertreter des Beschwerdeführers den Spieler mit Schreiben vom 21. Juli 2008 darauf hin, dass er seine arbeitsvertraglichen Pflichten gegenüber dem Verein verletze und daher schadenersatzpflichtig werde.
Am 22. Juli 2008 reiste Z._ von Deutschland ab, um sich der F._ Nationalmannschaft in Peking anzuschliessen. Am gleichen Tag forderte der Rechtsvertreter des Beschwerdeführers den Beschwerdegegner zur Abgabe einer schriftlichen Erklärung auf, mit der sich Letzterer unter anderem dazu verpflichten sollte, keinen weiteren Druck auf den Spieler auszuüben und kündigte rechtliche Schritte an, sollte die Erklärung nicht bis zum 23. Juli 2008 vorliegen.
Am 23. Juli 2008 erging das Rundschreiben 1153 der FIFA, das sich zur Frage der Freistellung von Fussballspielern für die Olympischen Spiele 2008 dahingehend äusserte, dass Spieler unter 23 Jahren für die Spiele in Peking freizustellen seien. Am 29. Juli 2008 sprach sich auch das Emergency Committee der FIFA zugunsten einer solchen Pflicht zur Freistellung aus.
Am 6. August 2008 erging ein Entscheid des Tribunal Arbitral du Sport (TAS) betreffend verschiedene Verfahren des Beschwerdeführers sowie weiterer Fussballvereine gegen die FIFA, in dem das TAS unter anderem erwog, dass den Beschwerdeführer keine rechtliche Verpflichtung zur Freistellung des Spielers Z._ für das olympische Fussballturnier 2008 in Peking treffe. Ein Angebot des Beschwerdeführers vom gleichen Tag, den Spieler gegen Bezahlung sowie Gewährleistung einer bestimmten Versicherungsdeckung für die Olympischen Spiele freizustellen, blieb vom Beschwerdegegner unbeantwortet.
A.c Am 11. August 2008 erhob der Beschwerdeführer beim FIFA Players' Status Committee Klage gegen den Beschwerdegegner und beantragte im Wesentlichen, der Beschwerdegegner sei dazu zu verpflichten, den Spieler Z._ weder für die Vorbereitungstrainings noch für das olympische Fussballturnier zu engagieren und ihn umgehend zum Beschwerdeführer zurückreisen zu lassen. Zudem sei eine Schadenersatzzahlung von EUR 50'000.-- an die Stiftung "G._" für jeden zusätzlichen Tag ab Urteilsfällung vorzusehen, an dem der Spieler Z._ im Vorbereitungstraining oder im olympischen Fussballturnier eingesetzt werde sowie eine Zahlung von EUR 26'600.-- für jeden Tag ab dem 23. Juli 2008 bis zur Urteilsfällung.
Die FIFA teilte dem Beschwerdeführer mit Schreiben vom 12. August 2008, das vom Head of Legal Affairs sowie vom Head of Players' Status unterzeichnet wurde, mit, dass sie sich nicht in der Lage sehe, in dieser Angelegenheit einzuschreiten.
B. Der Beschwerdeführer focht das Schreiben der FIFA vom 12. August 2008 noch am gleichen Tag beim TAS an und beantragte, der Entscheid sei aufzuheben und den der FIFA unterbreiteten Begehren sei stattzugeben. Mit ergänzendem Statement of Appeal vom 14. August 2008 passte der Beschwerdeführer unter anderem seine Zahlungsbegehren an, beantragte jedoch weiterhin in erster Linie die Aufhebung des angefochtenen Entscheids.
Das TAS entschied mit Schiedsspruch vom 16. Dezember 2008, dass der Appeal bezüglich des Schreibens der FIFA vom 12. August 2008 unzulässig sei und wies alle weiteren Rechtsbegehren ab. Das TAS erwog unter Hinweis auf R47 des TAS Code de l'arbitrage en matière de sport sowie Artikel 63.1 der Statuten der FIFA, dass ein Appeal nur gegen einen Entscheid zulässig sei. Das Schreiben der FIFA vom 12. August 2008 berühre die Rechtsstellung der Parteien jedoch nicht, sondern habe lediglich informativen Charakter und greife allfälligen Entscheidungen der zuständigen Organe der FIFA in dieser Angelegenheit nicht vor, weshalb es sich dabei nicht um eine Entscheidung handle, die beim TAS angefochten werden könne.
C. Mit Beschwerde in Zivilsachen beantragt der Beschwerdeführer dem Bundesgericht, es sei der Entscheid des TAS vom 16. Dezember 2008 aufzuheben und die Sache an das TAS, eventualiter an das Players' Status Committee der FIFA, zurückzuweisen.
Sowohl der Beschwerdegegner als auch die Vorinstanz schliessen auf Abweisung der Beschwerde.

Erwägungen:
1. Der angefochtene Entscheid ist in englischer Sprache ergangen. Die Parteien bedienen sich im Verfahren vor Bundesgericht der deutschen Sprache. Nach <ref-law> ist der Entscheid in der Amtssprache Deutsch zu begründen.
2. Im Bereich der internationalen Schiedsgerichtsbarkeit ist die Beschwerde in Zivilsachen unter den Voraussetzungen der Art. 190-192 IPRG zulässig (<ref-law>).
2.1 Der Sitz des Schiedsgerichts befindet sich vorliegend in Lausanne. Keine der Parteien hat ihren Sitz in 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).
2.2 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 mit Hinweis). Bei Rügen nach <ref-law> 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 S. 382).
2.3 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 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 <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).
Der Beschwerdeführer stellt seinen rechtlichen Ausführungen eine ausführliche Sachverhaltsdarstellung voran, in der er den Ablauf der Ereignisse sowie des Verfahrens aus seiner Sicht darlegt. Er weicht darin in zahlreichen Punkten von den tatsächlichen Feststellungen der Vorinstanz ab oder erweitert diese, ohne substantiiert Ausnahmen von der Sachverhaltsbindung gemäss Art. 105 Abs. 2 und Art. 97 Abs. 1 BGG geltend zu machen. Seine Vorbringen haben insoweit unbeachtet zu bleiben.
3. Nach <ref-law> kann gegen einen internationalen Schiedsspruch eingewendet werden, das Schiedsgericht habe über Streitpunkte entschieden, die ihm nicht unterbreitet worden seien oder es habe Rechtsbegehren unbeurteilt gelassen.
3.1 Der Beschwerdeführer beruft sich auf den zweiten Teil dieses Rügegrundes. Er macht geltend, wenn das Schreiben der FIFA vom 12. August 2008 einen Entscheid darstelle, was entgegen der Ansicht des TAS der Fall sei, so bestehe ein Anfechtungsgegenstand und der Entscheid der Vorinstanz stelle einen Verstoss gegen das Verbot dar, ein Rechtsbegehren unbeurteilt zu lassen. Der Beschwerdeführer führt in der Folge aus, inwiefern seine rechtliche Stellung durch das Schreiben vom 12. August 2008 tangiert worden sei und aus welchen Gründen es sich dabei um einen Nichteintretensentscheid handle. Daraus leitet er ab, es habe entgegen dem angefochtenen Entscheid ein Anfechtungsgegenstand vorgelegen, weshalb die Vorinstanz seine Rechtsbegehren unzulässigerweise unbeurteilt gelassen habe.
3.2 Die Rüge geht fehl. Die Vorinstanz ist mittels Auslegung des Schreibens der FIFA vom 12. August 2008 zum Schluss gelangt, dass dieses keine Rechtswirkungen entfalte, sondern lediglich informativer Natur sei. Damit fehle es an einem anfechtbaren Entscheid nach R47 des TAS Code de l'arbitrage en matière de sport sowie Artikel 63.1 der Statuten der FIFA, weshalb der erhobene Appeal unzulässig sei. Nachdem die Vorinstanz die Voraussetzungen eines Weiterzugs an das TAS verneinte, hat es den Appeal folgerichtig für unzulässig erklärt und hat auf eine Prüfung der weiteren Rechtsbegehren des Beschwerdeführers verzichtet. Der Beschwerdeführer stellt denn auch nicht in Frage, dass die Verneinung eines Anfechtungsobjekts diese Folge zeitigt; er wehrt sich vielmehr gegen die rechtliche Einordnung des Schreibens vom 12. August 2008 durch das TAS. Damit wird jedoch nicht die fehlende Beurteilung von Rechtsbegehren gerügt, sondern der Entscheid der Vorinstanz an sich in Frage gestellt, was im Rahmen von <ref-law> nicht zulässig ist (vgl. <ref-ruling> E. 4a S. 242 f.). Eine Verletzung von Zuständigkeitsbestimmungen nach <ref-law> macht der Beschwerdeführer nicht geltend.
4. Der Beschwerdeführer rügt weiter eine Verletzung des rechtlichen Gehörs sowie des Grundsatzes der Gleichbehandlung der Parteien (<ref-law>).
4.1 Er bringt zunächst vor, die Verneinung eines Anfechtungsgegenstandes durch das TAS sei nicht bloss unzutreffend, sondern widerspreche "in einer derart offensichtlichen Weise der Aktenlage, dass nachgerade eine formelle Rechtsverweigerung vorliege". Solche Konstellationen könnten praxisgemäss unter die Verletzung des rechtlichen Gehörs fallen, wenn das Gericht versehentlich eine aktenwidrige Annahme treffe; umso mehr müsse dies dann gelten, wenn die Aktenwidrigkeit geradezu mutwillig erfolge, wie dies vorliegend der Fall sei.
Die Rüge des Beschwerdeführers ist ungenügend begründet (<ref-law>). Abgesehen davon, dass aus seinen Vorbringen nicht klar wird, welche Tatsachenfeststellung der Vorinstanz aktenwidrig sein soll, verkennt er, dass nach der Rechtsprechung des Bundesgerichts eine offensichtlich falsche oder aktenwidrige Feststellung für sich allein nicht ausreicht, um einen internationalen Schiedsentscheid aufzuheben. Der Beschwerdeführer hätte vielmehr aufzeigen müssen, inwiefern ihm ein richterliches 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). Dies hat er unterlassen, weshalb auf seine Vorbringen nicht einzutreten ist.
4.2 Soweit der Beschwerdeführer der Vorinstanz eine Verletzung des Grundsatzes der Gleichbehandlung der Parteien vorwirft, lassen sich seine Vorbringen nicht auf die für das Bundesgericht verbindlichen Sachverhaltsfeststellungen des angefochtenen Entscheids (<ref-law>) stützen. So geht aus dem angefochtenen Entscheid weder hervor, dass das Vorgehen der FIFA "offensichtlich eine parteiische Protektion" zugunsten des Beschwerdegegners war noch, dass sich die FIFA dazu entschlossen hätte, dem Beschwerdegegner "durch eine Blockierung der rechtlichen Vorstösse des Beschwerdeführers" "massive Schützenhilfe" zu leisten. Allein im Umstand, dass die Vorinstanz den Rechtsstandpunkt des Beschwerdegegners hinsichtlich der Anfechtbarkeit des Schreibens der FIFA vom 12. August 2008 teilte, ist kein Verstoss gegen den Grundsatz der Gleichbehandlung der Parteien (<ref-law>) zu erblicken. Die Rüge ist unbegründet, soweit überhaupt darauf eingetreten werden kann.
4.3 Der Beschwerdeführer erblickt eine Verletzung des rechtlichen Gehörs sodann darin, dass die Vorinstanz ihre Erwägungen unter anderem auf das Schreiben der FIFA vom 4. November 2008 gestützt habe, das dem TAS ohne entsprechende Aufforderung eingereicht worden sei. Dabei sei nicht abzusehen gewesen, dass die Vorinstanz dieses Schreiben "kurz darauf als einen entscheidenden Teil des Verhaltens der Vorinstanz qualifizieren und entsprechend gewichten würde". Indem die Vorinstanz ihren Entscheid auf das genannte Schreiben abgestützt habe, ohne den Parteien Gelegenheit zu geben, dazu Stellung zu nehmen, habe sie gegen den Grundsatz des rechtlichen Gehörs (<ref-law>) verstossen.
Der Beschwerdeführer stellt selbst nicht in Abrede, dass ihm das Schreiben der FIFA vom 4. November 2008 von der Vorinstanz am 5. November 2008 zur Kenntnisnahme zugestellt worden war. Der angefochtene Entscheid erging am 16. Dezember 2008. Der Beschwerdeführer hätte somit mehr als einen Monat Zeit gehabt, sich zum genannten Schreiben zu äussern. Inwiefern es dem Beschwerdeführer nicht möglich gewesen wäre, innerhalb dieses Zeitraums zum Schreiben der FIFA Stellung zu nehmen, falls er dies für erforderlich gehalten hätte, ist nicht einzusehen. Die Rüge der Gehörsverletzung ist unbegründet.
5. Der Beschwerdeführer rügt schliesslich eine Verletzung des Ordre public (<ref-law>).
5.1 Soweit der Beschwerdeführer zur Begründung vorträgt, das Schreiben der FIFA vom 4. November 2008 erweise sich "im gesamten Kontext der Ereignisse" als Versuch, auf das TAS "einen ungebührlichen Druck auszuüben", stösst die Rüge ins Leere. Die FIFA teilte dem TAS im besagten Schreiben mit, dass sie darauf verzichte, als Partei am Schiedsverfahren teilzunehmen und äusserte ihre Rechtsauffassung zur Anfechtbarkeit ihres Schreibens vom 12. August 2008. Der Beschwerdeführer legt weder allgemein noch hinsichtlich des Schreibens vom 4. November 2008 hinreichend dar, worin eine ungebührliche Druckausübung auf die Vorinstanz bestanden haben soll. Von einer Verletzung des Ordre public kann keine Rede sein.
5.2 Der Beschwerdeführer begründet seine Rüge der Verletzung des Ordre public schliesslich damit, die Vorinstanz habe sich nicht auf das von den Parteien gestützt auf die FIFA-Statuen gewählte Recht, sondern auf ein falsches Recht abgestützt.
Unabhängig von der Frage, ob die Anwendung einer unzutreffenden Rechtsordnung überhaupt eine Verletzung des Ordre public darstellt, kann den Ausführungen des Beschwerdeführers nicht gefolgt werden. So anerkennt der Beschwerdeführer selber, dass die Vorinstanz zutreffend zum Schluss gelangt sei, auf die zu beurteilende Streitigkeit seien die FIFA-Regeln sowie zusätzlich Schweizer Recht anwendbar. Sein Vorwurf, die Vorinstanz habe die Frage, ob das Schreiben der FIFA vom 12. August 2008 eine anfechtbare Entscheidung darstelle, unter Missachtung des anwendbaren Rechts lediglich nach der eigenen Spruchpraxis und damit nach "TAS-Recht" beurteilt, verfängt nicht. So ist entgegen der in der Beschwerde geäusserten Behauptung nicht erkennbar, dass die Vorinstanz auf eine unzutreffende Rechtsordnung abgestellt hätte. Vielmehr zielt die Rüge des Beschwerdeführers darauf ab, blosse Kritik an der Rechtsanwendung der Vorinstanz zu üben, was im Rahmen der Schiedsbeschwerde nicht zulässig ist. Eine Verletzung des Ordre public ist nicht ersichtlich.
6. Die Beschwerde erweist sich als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend wird der 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. 7'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat den Beschwerdegegner für das bundesgerichtliche Verfahren mit Fr. 8'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Tribunal Arbitral du Sport (TAS) schriftlich mitgeteilt.
Lausanne, 23. Juni 2009
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Leemann