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.

Considérant en droit:
1. La loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE; RS 1 113) a été abrogée par l'entrée en vigueur, le 1er janvier 2008, de la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20; cf. ch. I de l'annexe à l'art. 125 LEtr). Selon l'art. 126 al. 1 LEtr, les demandes déposées avant l'entrée en vigueur de la nouvelle loi sont régies par l'ancien droit (cf., au sujet de l'interprétation de cette disposition, arrêts 2C_329/2009 du 14 septembre 2009 consid. 2.1 et 2C_98/2009 du 10 juin 2009 consid. 1.4). Le présent litige porte sur l'approbation de la prolongation de l'autorisation de séjour du recourant. La demande de prolongation et celle d'approbation sont antérieures au 1er janvier 2008, puisque l'Office fédéral a pu statuer le 16 mai 2007. Par conséquent, il y a lieu d'appliquer l'ancien droit en l'espèce.
2. Le Tribunal fédéral examine d'office sa compétence (<ref-law>). Il contrôle librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1. p. 96).
2.1 Selon l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions relatives à une autorisation de droit des étrangers à laquelle ni le droit fédéral ni le droit international ne donnent droit.
D'après l'art. 7 al. 1 LSEE, le conjoint étranger d'un ressortissant suisse a droit à l'octroi et à la prolongation de l'autorisation de séjour ainsi que, après un séjour régulier et ininterrompu de cinq ans, à l'autorisation d'établissement. Pour juger de la recevabilité du recours, seule est déterminante la question de savoir si un mariage au sens formel existe (arrêt 2C_454/2009 du 19 octobre 2009 consid. 2.1; cf. aussi <ref-ruling> consid. 1.1.2 p. 148). Cette condition n'est pas remplie actuellement, puisque le divorce des époux X._ a été prononcé le 16 août 2006 et qu'il est définitif et exécutoire depuis le 25 septembre 2006. En revanche, au moment décisif, soit le 2 décembre 2005 - date correspondant à un séjour régulier et ininterrompu de cinq ans conformément à l'art. 7 al. 1 2ème phrase LSEE -, le recourant était encore marié à une Suissesse et vivait depuis cinq ans en Suisse au bénéfice d'une autorisation de séjour. Ainsi, avant son divorce, le recourant pouvait prétendre à l'octroi d'une autorisation d'établissement; par conséquent, il jouit d'un droit à la prolongation de son autorisation de séjour, après son divorce (<ref-ruling> consid. 1.1.4 p. 149). Dès lors, le présent recours est recevable comme recours en matière de droit public, au regard de l'art. 83 let. c ch. 2 LTF (cf. <ref-ruling> consid. 1.2.2 p. 4; <ref-ruling> consid. 1.1.5 p. 149 s.).
2.2 Au surplus, le recours est dirigé contre une décision finale (<ref-law>), rendue dans une cause de droit public (<ref-law>) par le Tribunal administratif fédéral (<ref-law>). Il a été déposé en temps utile (art. 100 al. 1 et 46 al. 1 let. b LTF) et dans les formes prescrites (<ref-law>) par le destinataire de l'arrêt attaqué qui a un intérêt digne de protection à son annulation ou à sa modification (<ref-law>). Il convient donc d'entrer en matière.
3. Saisi d'un recours en matière de droit public, le Tribunal fédéral examine librement la violation du droit fédéral (cf. art. 95 let. a et 106 al. 1 LTF), sous réserve des exigences de motivation figurant à l'<ref-law>. Il y procède en se fondant sur les faits constatés par l'autorité précédente (cf. <ref-law>), à moins que ces faits n'aient été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (cf. <ref-law>). Le recourant doit expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'<ref-law> seraient réalisées, faute de quoi il n'est pas possible de tenir compte d'un état de fait qui diverge de celui qui est contenu dans l'acte attaqué (<ref-ruling> consid. 6.2 p. 288).
4. 4.1 D'après l'art. 7 LSEE, le conjoint étranger d'un ressortissant suisse a droit à l'octroi et à la prolongation de l'autorisation de séjour (al. 1 1ère phrase) puis, après un séjour régulier et ininterrompu de cinq ans, à l'autorisation d'établissement (al. 1 2ème phrase), à moins que le mariage n'ait été contracté dans le but d'éluder les dispositions sur le séjour et l'établissement des étrangers (al. 2), sous réserve au surplus d'un abus de droit (<ref-ruling> consid. 4.1 p. 267). Il y a abus de droit lorsque le conjoint étranger invoque un mariage n'existant plus que formellement dans le seul but d'obtenir une autorisation de police des étrangers, car ce but n'est pas protégé par l'art. 7 al. 1 LSEE (<ref-ruling> consid. 4.2 p. 267). Le mariage n'existe plus que formellement lorsque l'union conjugale est définitivement rompue, c'est-à-dire lorsqu'il n'y a plus d'espoir de réconciliation; les causes et les motifs de la rupture ne jouent pas de rôle (<ref-ruling> consid. 4.2 p. 117).
4.2 Le Tribunal administratif fédéral a retenu que le mariage du recourant avec une Suissesse n'avait plus existé que formellement à partir du mois de décembre 2004. Il a aussi constaté que, depuis lors, il n'y avait pas eu un espoir tangible de reprise de la communauté conjugale jusqu'au prononcé du jugement de divorce. Le recourant ne conteste pas avoir cessé la cohabitation avec son épouse suisse en décembre 2004. Il n'invoque aucun élément concret et vraisemblable permettant d'admettre qu'il existait, avant l'échéance du délai de cinq ans figurant à l'art. 7 al. 1 2ème phrase LSEE, une volonté de reprendre à court terme la vie commune. Il n'allègue du reste pas avoir entrepris à l'époque des démarches en ce sens. Dans ces circonstances, le Tribunal administratif fédéral pouvait estimer que, depuis sa séparation d'avec sa femme, en décembre 2004, l'intéressé ne pouvait plus se prévaloir de son mariage avec une Suissesse pour obtenir le renouvellement de son autorisation de séjour, sous peine de commettre un abus de droit.
4.2.1 Le recourant fait valoir que la rupture du lien conjugal ne remonterait pas à décembre 2004, mais au 16 août 2006, date du prononcé du divorce, ou, à la rigueur, au 29 mai 2006, date du dépôt de la requête commune de divorce. Il explique que la séparation antérieure à cette procédure de divorce était simplement un temps de réflexion.
Certes, si le Tribunal administratif fédéral avait dû se prononcer en décembre 2004, il n'aurait pas encore pu constater que l'union conjugale des époux X._ était définitivement rompue. Toutefois, à l'échéance du délai de cinq ans de l'art. 7 al. 1 2ème phrase LSEE, soit le 2 décembre 2005, la situation du couple n'avait pas changé. Or, il s'était écoulé suffisamment de temps pour que la rupture apparaisse irrémédiable, en l'absence de toute intention de reprendre la cohabitation. En outre, à ce moment, il était possible de faire remonter la rupture définitive du lien conjugal à la séparation de décembre 2004, puisque la communauté conjugale avait cessé à ce moment. On ne saurait suivre le recourant qui considère qu'il faut attendre le prononcé du divorce ou, à tout le moins, le début de la procédure de divorce pour admettre la rupture définitive du lien conjugal. Ce serait oublier que l'art. 7 al. 1 1ère et 2ème phrases LSEE a pour but de protéger une véritable communauté conjugale, même si la cohabitation des époux n'est pas exigée. Cette disposition tend en effet à permettre et assurer juridiquement la vie commune en Suisse, soit la vie auprès de l'époux suisse du conjoint étranger (<ref-ruling> consid. 4.3 p. 268).
4.2.2 Le recourant prétend que, si la rupture définitive de l'union conjugale était intervenue déjà en décembre 2004, son épouse de nationalité suisse n'aurait pas attendu jusqu'à la fin du mois de mai 2006 pour engager une procédure judiciaire en divorce ou en mesures protectrices de l'union conjugale.
Cet argument n'est pas convaincant. En réalité, le comportement adopté par la femme du recourant est précisément de nature à étayer la thèse de l'abus de droit. La chronologie des événements laisse à penser qu'en dépit de la rupture définitive de l'union conjugale, l'épouse n'a pas voulu nuire à son mari en entamant une procédure judiciaire avant - voire juste après - l'échéance du délai de cinq ans de l'art. 7 al. 1 2ème phrase LSEE.
4.2.3 Le recourant reproche au Tribunal administratif fédéral de n'avoir "pas pris en compte plusieurs éléments et indices". En particulier, selon lui, cette autorité n'a pas établi qu'il aurait eu une liaison adultère avant l'échéance du délai de cinq ans de l'art. 7 al. 1 2ème phrase LSEE et elle aurait dû voir là un indice important pour nier un prétendu abus de droit, au lieu de l'ignorer.
Le recourant s'en prend ainsi à la façon dont le Tribunal administratif fédéral a établi les faits. Force est de constater que cette autorité n'a pas établi si l'intéressé avait une relation avec une tierce personne avant le 2 décembre 2005. Il ressort toutefois du dossier que, lors de son audition du 7 décembre 2005 par le Service cantonal, l'intéressé a lui-même admis avoir eu une nouvelle compagne, tout en ajoutant que cette relation était finie. Il a aussi déclaré savoir que sa femme avait un nouveau compagnon. En présence de ces éléments qui ne font que conforter la théorie de l'abus de droit, on ne voit manifestement pas en quoi le Tribunal administratif fédéral aurait méconnu des faits pertinents en ne s'intéressant pas aux éventuelles relations du recourant avant décembre 2005.
4.3 En conclusion, le Tribunal administratif fédéral n'a pas violé le droit fédéral, en particulier l'art. 7 LSEE, en rendant l'arrêt attaqué.
5. Au vu de ce qui précède, il y a lieu de rejeter le recours.
Succombant, le recourant doit supporter les frais judiciaires (art. 65 et 66 al. 1 LTF) et n'a pas droit à des dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
3. Le présent arrêt est communiqué au mandataire du recourant, à l'Office fédéral des migrations, au Tribunal administratif fédéral, Cour III, ainsi qu'au Service de la population et des migrants du canton de Fribourg.
Lausanne, le 3 décembre 2009
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Müller Dupraz