Faits: A. Ressortissant kosovar né en 1971, A.X._ a déposé une demande d'asile en Suisse le 29 décembre 1998. Par décision du 20 avril 2000, l'Office fédéral des réfugiés actuellement l'Office fédéral des migrations (ci-après: l'Office fédéral) a rejeté cette requête et prononcé le renvoi de Suisse de l'intéressé. Sur recours, cette décision a été confirmée le 14 juillet 2000. A.X._ s'est alors vu impartir un délai de départ échéant le 13 septembre 2000. Le 2 décembre 2000, A.X._ a épousé B._, une Suissesse née en 1957. Il s'est par conséquent vu octroyer, au titre du regroupement familial, une autorisation de séjour qui a été régulièrement prolongée. Le 18 octobre 2005, A.X._ a requis une autorisation d'établissement. Le 7 décembre 2005, le Service de la population et des migrants du canton de Fribourg (ci-après: le Service cantonal) a entendu les époux X._ qui ont, tous les deux, déclaré vivre séparément depuis le mois de décembre 2004. Par courrier du 9 février 2006, le Service cantonal a fait savoir à A.X._ qu'il ne pourrait bénéficier d'une autorisation d'établissement qu'à partir du 1er décembre 2010 et a prolongé son autorisation de séjour jusqu'au 1er décembre 2006. Le mariage des époux X._ a été dissous par jugement du 16 août 2006, devenu définitif et exécutoire le 25 septembre 2006. Le 13 décembre 2006, A.X._ a épousé une femme vivant en Ouzbékistan. Le 3 avril 2007, le Service cantonal a informé A.X._ qu'il était favorable à la poursuite de son séjour dans le canton de Fribourg, sous réserve de l'approbation de l'Office fédéral. Par décision du 16 mai 2007, l'Office fédéral a refusé d'approuver la prolongation de l'autorisation de séjour de A.X._ et prononcé son renvoi de Suisse. Il a notamment retenu que l'intéressé ne pouvait plus se prévaloir de son mariage, vidé de toute substance depuis le mois de décembre 2004, pour poursuivre son séjour en Suisse. Au surplus, il a examiné l'octroi à A.X._ d'une autorisation de séjour dans le cadre de la libre appréciation de l'autorité. Le 13 mars 2009, A.X._ a été condamné, pour vol par métier, à une peine privative de liberté de 10 mois, avec sursis pendant 3 ans. B. Par arrêt du 12 juin 2009, le Tribunal administratif fédéral a rejeté, dans la mesure où il était recevable, le recours de A.X._ contre la décision de l'Office fédéral du 16 mai 2007. Il a repris l'argumentation de cette autorité, en précisant qu'à partir de décembre 2004, l'intéressé ne pouvait plus invoquer son mariage pour obtenir le renouvellement de son autorisation de séjour, sans commettre un abus de droit. C. Le 17 août 2009, A.X._ a déposé au Tribunal fédéral un recours en matière de droit public à l'encontre de l'arrêt du Tribunal administratif fédéral du 12 juin 2009. Il conclut, sous suite de frais et dépens, à l'annulation de l'arrêt attaqué et à l'approbation de la prolongation de son autorisation de séjour. Il conteste tout abus de droit et se plaint d'une mauvaise application du droit fédéral. Le Tribunal administratif fédéral a renoncé à se déterminer sur le recours. L'Office fédéral conclut au rejet du recours. A la demande du Tribunal fédéral, le Service cantonal a produit son dossier. D. Par ordonnance du 20 août 2009, le Juge présidant la IIe Cour de droit public a admis la demande d'effet suspensif contenue dans le recours.