Faits:
A. A.X._, ressortissant kosovar né en 1975, est arrivé en Suisse le 5 mars 1993. Sa demande d'asile du 10 mars 1993 a été rejetée le 3 juin 1993. Il a toutefois fait l'objet d'une admission provisoire jusqu'en 1998, date à laquelle le Conseil fédéral a décidé de lever l'admission provisoire collective des déserteurs et réfractaires provenant de l'ex-Yougoslavie. Un délai au 15 janvier 1999 lui a été imparti pour quitter le pays.
Le 26 février 1999, l'intéressé a épousé une Suissesse, B._, et a de ce fait obtenu une autorisation de séjour, régulièrement renouvelée jusqu'au 25 février 2005.
Le 30 novembre 2000, B._ a déposé une demande unilatérale de divorce, à laquelle son époux s'est opposé. Elle s'est constitué un domicile séparé dès le 31 décembre 2000. Le 7 mai 2001, le Tribunal civil de la Glâne a autorisé la séparation de corps des époux X._. Le 27 novembre 2001, B._ a déposé un nouvelle demande unilatérale de divorce et le 23 décembre 2001, elle a donné naissance à une fille issue de la relation qu'elle avait entre-temps nouée avec un tiers.
Le 24 février 2002, C._, ressortissante kosovare née en 1984, enceinte de A.X._, est entrée en Suisse et y a demandé l'asile. Sa requête a été rejetée par l'Office fédéral des migrations (ci-après: l'Office fédéral) puis par la Commission de recours en matière d'asile, tant en procédure ordinaire, les 18 mars et 3 juillet 2002, que sur réexamen, les 13 mars et 16 mai 2003. Le 27 septembre 2002, l'intéressée a accouché d'un fils, D._, reconnu par A.X._ le 19 août 2004.
Par jugement du 8 septembre 2004, le Tribunal d'arrondissement de la Sarine a prononcé le divorce des époux X._.
B. Le 7 janvier 2005, A.X._ a épousé C._ et a déposé, le 28 janvier 2005, une demande de regroupement familial en faveur de sa femme et de son fils.
Le 20 juin 2005, le Service cantonal a refusé de renouveler l'autorisation de séjour de l'intéressé et d'autoriser le séjour de C.X._ et A.X._. Les intéressés ont recouru contre cette décision auprès du Tribunal administratif du canton de Fribourg (ci-après: le Tribunal cantonal), qui a admis leur recours le 29 mars 2006. De ce fait, le Service cantonal a informé la famille X._ qu'il était disposé à autoriser leur séjour en Suisse, sous réserve de l'approbation de l'Office fédéral.
Par décision du 23 août 2006, l'Office fédéral a refusé son approbation à la prolongation de l'autorisation de séjour de A.X._ et a prononcé son renvoi de Suisse. Il n'est pas entré en matière sur la demande d'approbation à l'octroi d'une autorisation de séjour initiale en faveur de C.X._ et D.X._, en raison du rejet de leur demande d'asile et en l'absence d'un droit à une autorisation de séjour. Le renvoi de Suisse de ces derniers a été exécuté le 3 mars 2007.
C. Par arrêt du 15 septembre 2008, le Tribunal administratif fédéral a rejeté le recours de A.X._ contre la décision de l'Office fédéral du 23 août 2006, dans la mesure où il était recevable. Il a considéré pour l'essentiel que l'Office fédéral n'était pas lié par les décisions des autorités cantonales et pouvait parfaitement s'écarter de l'appréciation de ces dernières; il n'avait donc pas violé le principe de la séparation des pouvoirs. Par ailleurs, l'intéressé commettait un abus de droit en se prévalant d'un mariage qui n'existait plus que formellement, avant l'écoulement du délai de cinq ans, dans le seul but d'obtenir une autorisation de séjour. En outre, l'Office fédéral n'avait pas outrepassé son pouvoir d'appréciation en refusant de donner son approbation à la prolongation de l'autorisation sollicitée.
D. Agissant par la voie du recours en matière de droit public, A.X._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'arrêt du Tribunal administratif fédéral du 15 septembre 2008 et d'approuver la prolongation de son autorisation de séjour. Il fait valoir une constatation inexacte des faits et une mauvaise application du droit fédéral. Il se plaint en outre de la violation de son droit d'être entendu. A l'appui de ses griefs, il invoque également l'art. 8 par. 1 CEDH.
Le Tribunal administratif fédéral a renoncé à prendre position sur le recours. L'Office fédéral a proposé le rejet du recours. Le 5 janvier 2009, le Service cantonal a fait parvenir son dossier.

Considérant en droit:
1. La loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20) est entrée en vigueur le 1er janvier 2008 (RO 2007 5487). En vertu de l'art. 126 al. 1 LEtr, les demandes déposées avant l'entrée en vigueur de la loi sont régies par l'ancien droit. En l'espèce, la décision par laquelle l'Office fédéral a refusé d'approuver le renouvellement de l'autorisation de séjour du recourant a été rendue avant l'entrée en vigueur de la loi précitée. Par analogie, la présente affaire doit ainsi être examinée sous l'angle de l'ancienne loi fédérale sur le séjour et l'établissement des étrangers (LSEE; RS 1 113 et les modifications ultérieures). La procédure est en revanche régie par le nouveau droit (art. 126 al. 2 LEtr).
2. D'après l'art. 83 lettre c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions en matière de droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit.
2.1 En vertu de 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. Dans la mesure où son mariage avec une ressortissante suisse a été dissous par le divorce, le recourant n'a pas droit au renouvellement de son autorisation de séjour. Toutefois, son union ayant duré plus de cinq ans, il a en principe droit à une autorisation d'établissement (cf. <ref-ruling> consid. 3b p. 147). Son recours est donc recevable sous cet angle.
2.2 Le recourant invoque également l'art. 8 CEDH. Un étranger peut, selon les circonstances, se prévaloir du droit au respect de la vie privée et familiale garanti par cette disposition pour s'opposer à l'éventuelle séparation de sa famille et obtenir ainsi une autorisation de séjour. Encore faut-il, pour pouvoir invoquer la protection de la vie familiale découlant de l'art. 8 CEDH, que la relation entre l'étranger et une personne de sa famille ayant le droit de résider durablement en Suisse - en principe nationalité suisse ou autorisation d'établissement - soit étroite et effective (cf. <ref-ruling> consid. 3.1 p. 285 s. et les références). Par ailleurs, pour pouvoir déduire de la protection de la vie privée garantie par l'art. 8 CEDH un droit de résider en Suisse, il faut avoir tissé des relations privées spécialement intenses avec ce pays. Le Tribunal fédéral a considéré qu'une présence en Suisse d'environ seize ans et les liens privés habituels qui en découlent ne fondaient pas encore à eux seuls des relations particulièrement intenses et ne créaient par conséquent pas un droit à une autorisation (<ref-ruling> consid. 2c/aa p. 384 s.).
Le recourant ne peut faire valoir aucune relation étroite et effective avec une personne de sa famille ayant le droit de résider durablement en Suisse. De plus, l'intéressé, qui est arrivé en Suisse en 1993, a été admis provisoirement jusqu'en 1999, et n'est toléré depuis le 25 février 2005 qu'en raison des procédures qu'il a entamées, ne peut pas invoquer des relations privées exceptionnellement intenses avec la Suisse. Par conséquent, dans la mesure où il se prévaut de l'art. 8 CEDH pour demander l'octroi d'une autorisation de séjour en sa faveur, son recours est irrecevable.
2.3 Par ailleurs, le recourant fait grief au Tribunal administratif fédéral de n'avoir pas suffisamment tenu compte, dans la pesée des intérêts, de la durée de son séjour en Suisse, de sa bonne intégration ainsi que de l'absence d'attaches avec son pays d'origine. Or, il s'agit là de critères dont l'Office fédéral et le Tribunal administratif fédéral se sont servis pour statuer selon leur libre appréciation (art. 4 LSEE) sur le maintien de l'autorisation de séjour. A cet égard, le recourant ne peut pas faire valoir de droit à ladite autorisation, de sorte que la voie du recours en matière de droit public n'est pas ouverte sur ce point (art. 83 let. c ch. 2 LTF; cf. <ref-ruling> consid. 2.1. p. 284; 388 consid. 1.1 p. 389 s. et les références).
3. Selon l'<ref-law>, le recourant peut critiquer les constatations de faits à la double condition que ceux-ci aient été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> et que la correction du vice soit susceptible d'influer sur le sort de la cause, ce qu'il doit rendre vraisemblable par une argumentation répondant aux exigences des art. 42 al. 2 et 106 al. 2 LTF (<ref-ruling> consid. 1.4.3 p. 254 s.).
En l'espèce, le recourant reproche à l'autorité intimée d'avoir établi les faits de manière inexacte en relevant qu'il avait caché sa relation avec la mère de son enfant jusqu'à leur mariage le 7 janvier 2005. Il est douteux que la motivation du grief réponde aux exigences précitées. Quoi qu'il en soit, il ressort de l'arrêt attaqué (partie "faits", lettre I) que cet élément constitue en réalité l'un des motifs pour lesquels l'Office fédéral avait envisagé de refuser son approbation au renouvellement de l'autorisation de séjour de l'intéressé. Cette circonstance n'a au demeurant pas été déterminante pour l'issue du litige, le Tribunal administratif fédéral ayant simplement considéré que les époux X._ avaient tous les deux très rapidement refait leur vie avec un nouveau partenaire (consid. 8.3.1 p. 12). Par conséquent, le grief d'établissement inexact des faits doit être rejeté dans la mesure de sa recevabilité.
4. 4.1 Dans un moyen intitulé violation du droit d'être entendu, le recourant se plaint que l'Office fédéral s'est "substitué" à l'arrêt rendu par le Tribunal administratif du canton de Fribourg qui, de son côté, avait admis son recours. A son avis, lorsqu'un tribunal cantonal admet un recours contre une décision négative de l'administration cantonale en matière d'autorisation de séjour, l'autorité administrative fédérale n'est plus à même de refuser son approbation.
Il apparaît que le grief est sans rapport avec les garanties découlant du droit d'être entendu. Le recourant fait plutôt valoir un vice de procédure, à savoir une mauvaise répartition des compétences entre autorités ou la violation du principe de l'autorité de la chose jugée. La motivation déficiente de ce grief au regard des exigences de l'<ref-law> le rend ainsi irrecevable.
4.2 Au surplus, on ne voit pas sur quoi l'intéressé se base pour affirmer que l'Office fédéral ne peut pas refuser son approbation si la décision positive de l'autorité cantonale repose sur un arrêt de la dernière instance judiciaire cantonale. En effet, un tel mécanisme empêcherait l'Office fédéral de remplir sa mission telle qu'elle a été prévue par le législateur, à savoir d'assurer une pratique uniforme du droit fédéral.
Ainsi, comme l'a pertinemment exposé le Tribunal administratif fédéral, en raison de la répartition des compétences en matière de police des étrangers, il appartient aux cantons de statuer sur le refus initial d'une autorisation de séjour alors que la Confédération est chargée, en cas d'admission d'une demande d'autorisation de séjour ou d'établissement, de se prononcer sur cette autorisation dans un deuxième temps par la voie de la procédure d'approbation (cf. art. 99 en relation avec l'art. 40 al. 1 LEtr). L'art. 85 al. 1 let. a de l'ordonnance du 24 octobre 2007 relative à l'admission, au séjour et à l'exercice d'une activité lucrative (OASA; RS 142.201) précise à cet égard que l'Office fédéral a la compétence d'approuver l'octroi et le renouvellement des autorisations de séjour et de courte durée, ainsi que l'octroi de l'établissement, notamment lorsqu'il estime qu'une procédure d'approbation est nécessaire pour certaines catégories de personnes, afin d'assurer une pratique uniforme de la loi.
Cette procédure d'approbation ne diffère pas de celle qui prévalait sous la LSEE (cf. notamment art. 18 al. 3 et 4 LSEE; cf. Message du 8 mars 2002 concernant la loi sur les étrangers [FF 2002 p. 3469 ss], p. 3526 et p. 3578 s.), si bien que la pratique et la jurisprudence développées sous l'ancien droit gardent toute leur portée. Le Tribunal fédéral a ainsi déjà jugé que l'Office fédéral n'était pas lié par les considérations d'une autorité judiciaire cantonale en matière de police des étrangers et qu'il gardait la compétence de refuser son approbation, même s'il n'avait pas fait usage de son droit de recourir directement au Tribunal fédéral contre le jugement cantonal octroyant l'autorisation de séjour litigieuse (<ref-ruling> consid. 3 p. 51 ss et les nombreuses références).
Il s'ensuit que l'autorité intimée a correctement appliqué le droit fédéral en confirmant que l'Office fédéral avait la compétence de refuser son approbation dans le cas d'espèce. Mal fondé, le grief doit être écarté.
5. Au fond, le recourant conteste commettre un abus de droit en se prévalant de l'art. 7 al. 1 LSEE.
5.1 Selon l'art. 7 al. 1 1ère phrase LSEE, le conjoint étranger d'un ressortissant suisse a droit à l'octroi et à la prolongation de l'autorisation de séjour. D'après la jurisprudence, le conjoint étranger abuse de ce droit lorsqu'il invoque un mariage n'existant plus que formellement dans le seul but d'obtenir une autorisation de séjour, car cet objectif n'est pas protégé par l'art. 7 al. 1 LSEE (<ref-ruling> consid. 4.2 p. 267 et les références). Le mariage n'existe plus que formellement lorsque l'union conjugale est rompue définitivement, 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 et les références). De plus, après un séjour régulier et ininterrompu de cinq ans, le conjoint étranger d'un ressortissant suisse a en principe droit à une autorisation d'établissement. Celle-ci n'étant pas limitée dans le temps, un divorce éventuel ne pourra plus influencer le droit à l'établissement en Suisse de l'étranger. A l'échéance du délai de cinq ans, l'époux étranger n'a plus besoin de se référer au mariage. Pour refuser une autorisation d'établissement, l'abus de droit doit donc avoir existé avant l'écoulement de ce délai (<ref-ruling> consid. 4c p. 104 s.).
5.2 Il n'est pas contesté que A.X._ a épousé B._ en 1999, que cette dernière a déclaré avoir quitté son mari en août 2000 et que la séparation de corps des époux a été prononcée le 7 mai 2001. Par ailleurs, les intéressés ont tous les deux très rapidement refait leur vie avec un nouveau partenaire, B._ ayant eu un enfant d'une autre relation en 2001 et le recourant ayant rencontré, à peu près à cette époque, son épouse actuelle, dont il a eu un fils en septembre 2002. Ces éléments permettent d'établir que depuis 2001 ou 2002, la communauté conjugale entre les époux A.X._ et B.X._ n'était plus effective. Le recourant abuse donc manifestement de son droit en invoquant un mariage qui était vidé de sa substance bien avant l'échéance du délai de cinq ans. Dans ces circonstances, on ne saurait reprocher à l'autorité intimée d'avoir retenu que le comportement de l'intéressé, consistant à s'opposer au divorce introduit par son épouse, constituait une manoeuvre dilatoire pour prolonger artificiellement son séjour en Suisse. De toute façon, ce n'est pas ce dernier élément qui est déterminant en l'espèce, mais bien plutôt le fait que l'intéressé se prévaut d'une union conjugale qui n'était plus effective dans le seul but d'obtenir une autorisation de séjour.
6. Il résulte de ce qui précède que le recours doit être rejeté dans la mesure où il est recevable. 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é dans la mesure où il est recevable.
2. Les frais judiciaires, arrêtés à 1'800 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 et à la Cour III du Tribunal administratif fédéral ainsi que, pour information, au Service de la population et des migrations du canton de Fribourg.
Lausanne, le 15 janvier 2009
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Juge présidant: La Greffière:
T. Merkil F. Mabillard