Sachverhalt: A. A.a Y._, (Beschwerdegegner) ist ein erfolgreicher Langstreckenläufer. X._, (Beschwerdeführer) ist der nationale Leichtathletikverband von Z._ und als solcher Mitglied der International Association of Athletics Federations (IAAF). A.b Am 12. März 2006 wurde der Beschwerdegegner anlässlich des Marathons in Seoul, Südkorea, einer Dopingkontrolle unterzogen. Die Probe des Beschwerdegegners wurde in eine A- sowie eine B-Probe aufgeteilt und an das Doping Center of the Korea Institute of Science and Technology in Seoul gesandt, dessen Labor von der Welt-Anti-Doping-Agentur (WADA) anerkannt ist. Am 16. März 2006 wurde die A-Probe von A._ untersucht und es wurde die verbotene Substanz 19-Norandrosteron nachgewiesen. Am 13. April 2006 teilte die IAAF dem Beschwerdeführer das Testresultat mit und wies ihn an, nach Rule 37 der IAAF Competition Rules vorzugehen. Am 17. April 2006 teilte der Beschwerdeführer dem Beschwerdegegner das positive Testresultat mit und informierte ihn über sein Recht zur Prüfung der B-Probe. Der Beschwerdegegner bot keine Erklärung für den Nachweis von 19-Norandrosteron in seiner A-Probe an. Am 25. April 2006 wurde er vom Beschwerdeführer einstweilig für sämtliche Wettkämpfe gesperrt. Am 16. Mai 2006 wurde die B-Probe von A._ unter Aufsicht von Dr. B._ untersucht. Wiederum liess sich die Substanz 19-Norandrosteron nachweisen. B. B.a Am 10. September 2006 führte der Beschwerdeführer im Rahmen des Disziplinarverfahrens die erste Anhörung durch. Nach zahlreichen Verschiebungen fand am 11. Dezember 2008 eine weitere Anhörung vor einer neu zusammengesetzten Disziplinarkommission statt. Mit Schreiben vom 11. Dezember 2008 teilte der Beschwerdeführer dem Beschwerdegegner mit, dass die Disziplinarkommission einstimmig ein Dopingvergehen festgestellt und für den Zeitraum vom 25. April 2006 bis 11. Dezember 2008 eine Sperre ausgesprochen habe. Dabei wurden dem Beschwerdegegner sämtliche anlässlich der Teilnahme am Seoul Marathon 2006 erlangten Preise und Einnahmen aberkannt. B.b Der Beschwerdegegner focht den Entscheid der Disziplinarkommission des Beschwerdeführers vom 11. Dezember 2008 mit Eingabe vom 7. Januar 2009 beim Tribunal Arbitral du Sport (TAS) an. Er behauptete im Wesentlichen eine Verletzung von Art. 5.2.4.3.2.2 des "WADA Code International Standard for Laboratories", weil sowohl die A-Probe als auch die B-Probe von derselben Person (A._) durchgeführt worden war. Der Beschwerdeführer bestritt insbesondere die Zuständigkeit des TAS, da weder die Statuten noch die anderen anwendbaren Verbandsregeln eine Weiterzugsmöglichkeit an das TAS vorsähen. Das TAS erwog, dass seine Zuständigkeit nicht auf die Verbandsregeln des Beschwerdeführers gestützt werden könne. Es erklärte sich jedoch gestützt auf ein von Dr. C._, dem IAAF Anti-Doping Administrator, verfasstes und an den Rechtsvertreter des Beschwerdegegners gerichtetes Schreiben vom 10. April 2008 dennoch für zuständig. Mit Schiedsentscheid vom 24. Juli 2009 hiess das TAS die Berufung des Beschwerdegegners gut, es hob den Entscheid des Beschwerdeführers vom 11. Dezember 2008 auf und liess den Beschwerdegegner ohne weitere Untersuchung wieder zur Teilnahme an Wettkämpfen zu. C. Mit Beschwerde in Zivilsachen beantragt der Beschwerdeführer dem Bundesgericht, es sei der Schiedsspruch des TAS vom 24. Juli 2009 aufzuheben und es sei festzustellen, dass das TAS zur Beurteilung der Berufung des Beschwerdegegners nicht zuständig sei. Eventualiter sei das Verfahren an die Vorinstanz zurückzuweisen. Der Beschwerdegegner beantragt, es sei auf die Beschwerde nicht einzutreten, eventualiter sei diese abzuweisen. Das TAS schliesst auf Abweisung der Beschwerde. Der Beschwerdeführer reichte dem Bundesgericht eine Replik, der Beschwerdegegner eine Duplik ein. D. Mit Präsidialverfügung vom 16. November 2009 wurde das Gesuch des Beschwerdegegners um Sicherstellung einer allfälligen Parteientschädigung gutgeheissen. Der Beschwerdeführer überwies in der Folge den geforderten Betrag von Fr. 6'000.-- an die Bundesgerichtskasse. 