Faits:
A. X._, unique associé gérant de A._ a reçu, de la section « main-d'oeuvre étrangère » du Service de la population et des migrants (SPoMi), une décision du 1er juin 2006 permettant l'engagement de B._ dès l'obtention de son autorisation de séjour. X._ a employé le prénommé en qualité de ferrailleur une première fois du 5 au 30 juin 2006, puis une seconde fois du 30 octobre au 3 novembre 2006.
B. Par jugement du 20 novembre 2007, le Juge de police de l'arrondissement de la Sarine a condamné X._, pour violation de la LSEE, à une amende de 500 fr. et à une peine pécuniaire de 10 jours-amende à 50 fr. sans sursis. Il a renoncé à révoquer le sursis qui lui avait été accordé le 15 avril 2002 lorsqu'il l'avait condamné pour des faits similaires remontant à l'année 2000.
C. Par arrêt du 9 janvier 2009, la Cour d'appel pénal du Tribunal cantonal fribourgeois a réformé le jugement précité en ce sens qu'elle a condamné X._, pour délit à la LSEE, à une amende de 500 fr., la peine privative de liberté de substitution étant fixée à 5 jours.
D. X._ a déposé un recours en matière pénale. Invoquant l'arbitraire et une violation des art. 2 al. 2, 12, 13 CP, 23 al. 5 LSEE et 117 LEtr., il a conclu à son acquittement.
Le Tribunal cantonal et le Ministère public ont renoncé à déposer des observations.

Considérant en droit:
1. Les faits reprochés au recourant sont antérieurs à l'entrée en vigueur, le 1er janvier 2008, de la loi fédérale sur les étrangers (LEtr; RS 142.20).
1.1 Selon l'<ref-law>, la loi pénale ne s'applique qu'aux faits commis après son entrée en vigueur (principe de la non-rétroactivité de la loi pénale). Cependant, en vertu de l'<ref-law>, une loi nouvelle s'applique aux faits qui lui sont antérieurs si, d'une part, l'auteur est mis en jugement après son entrée en vigueur et si, d'autre part, elle est plus favorable à l'auteur que l'ancienne (exception de la lex mitior). L'art. 126 al. 4 LEtr précise également que les dispositions pénales de la présente loi s'appliquent aux infractions commises avant son entrée en vigueur lorsqu'elles sont plus favorables à leur auteur.
1.2 La Cour cantonale, qui a rendu l'arrêt attaqué postérieurement au 1er janvier 2008, était saisie d'un appel pénal, voie de droit ordinaire produisant un effet dévolutif complet (cf. <ref-ruling> consid. 6 p. 86 ss).
Aux termes de l'art. 23 LSEE, celui qui, intentionnellement, aura occupé des étrangers non autorisés à travailler en Suisse sera, en plus d'une éventuelle sanction en application de l'al. 1, puni pour chaque cas d'étranger employé illégalement d'une amende jusqu'à 5'000 fr. Celui qui aura agi par négligence sera puni d'une amende jusqu'à 3'000 fr. Dans les cas de très peu de gravité, il peut être fait abstraction de toute peine. Lorsque l'auteur a agi par cupidité, le juge peut infliger des amendes d'un montant supérieur à ces maximums (al. 4). Celui qui, ayant agi intentionnellement, aura déjà fait l'objet d'un jugement exécutoire selon l'art. 23 al. 4 et qui, en l'espace de cinq ans, occupera de nouveau un étranger illégalement, pourra être puni, en plus de l'amende, d'une peine pécuniaire de 180 jours-amende au plus (al. 5).
D'après l'art. 117 LEtr, quiconque, intentionnellement, emploie un étranger qui n'est pas autorisé à exercer une activité lucrative en Suisse ou a recours, en Suisse, à une prestation de services transfrontaliers d'une personne qui n'a pas l'autorisation requise est puni d'une peine privative de liberté d'un an au plus ou d'une peine pécuniaire. Dans les cas graves, la peine sera une peine privative de liberté de trois ans au plus ou une peine pécuniaire. En cas de peine privative de liberté, une peine pécuniaire est également prononcée (al. 1). Quiconque, ayant fait l'objet d'une condamnation exécutoire en vertu de l'al. 1, contrevient de nouveau, dans les cinq années suivantes, à l'al. 1, est puni d'une peine privative de liberté de trois ans au plus ou d'une peine pécuniaire. En cas de peine privative de liberté, une peine pécuniaire est également prononcée (al. 2).
1.2.1 Les dispositions précitées divergent sur deux points essentiels. D'une part, l'art. 117 LEtr ne punit que les actes commis intentionnellement, alors que l'art. 23 al. 4 LSEE sanctionne également la négligence (A. Zünd, in Spescha/Thür/Zünd/Bolzli, Kommentar Migrationsrecht, Zurich 2008, ad art. 117 LEtr n° 2 p. 256). D'autre part, le nouveau droit prévoit la peine privative de liberté, soit des sanctions plus sévères que sous l'ancienne loi.
1.2.2 Dès lors, si le recourant a agi par négligence, il doit être acquitté en vertu du nouveau droit. En revanche, si l'intention, qui comprend également le dol éventuel, doit être retenue, l'ancienne LSEE s'applique, les sanctions prévues étant alors plus favorables à l'intéressé.
2. Invoquant l'arbitraire et contestant notamment avoir agi de manière intentionnelle, le recourant estime que sa condamnation repose sur des faits inexacts et incomplets.
2.1 Une décision n'est pas arbitraire du seul fait qu'elle apparaît discutable ou même critiquable; il faut qu'elle soit manifestement insoutenable, et cela non seulement dans sa motivation mais dans son résultat (<ref-ruling> consid. 5.4 p. 148; <ref-ruling> consid. 3.1 p. 153). L'arbitraire allégué doit par ailleurs être suffisamment démontré, sous peine d'irrecevabilité (cf. <ref-law>; <ref-ruling> consid. 1.4 p. 287).
Le dol éventuel suppose que l'auteur, qui ne veut pas le résultat dommageable pour lui-même, envisage le résultat de son acte comme possible et l'accepte au cas où il se produirait (<ref-ruling> consid. 2.2 p. 4 s.; <ref-ruling> consid. 8.2 p. 61). La différence entre le dol éventuel et la négligence consciente réside dans la volonté de l'auteur. Celui qui agit par dol éventuel accepte le résultat dommageable pour le cas où il se produirait, alors que celui qui se rend coupable de négligence consciente escompte que le résultat dont il envisage l'avènement comme possible ne se produira pas (<ref-ruling> consid. 5a p. 3).
Savoir ce que l'auteur voulait, savait ou ce dont il s'accommodait relève du contenu de la pensée, donc de l'établissement des faits, lesquels ne peuvent être revus qu'aux conditions posées à l'<ref-law>. Toutefois, pour admettre le dol éventuel, le juge se fonde généralement sur des éléments extérieurs révélateurs. Il est admis à ce propos que les questions de fait et de droit interfèrent étroitement sur certains points. Parmi les éléments extérieurs permettant de conclure que l'auteur a accepté le résultat dommageable pour le cas où il se produirait figurent notamment la probabilité (connue de l'auteur) de la réalisation du risque et l'importance de la violation du devoir de prudence. Plus celles-ci sont grandes, plus sera fondée la conclusion que l'auteur, malgré d'éventuelles dénégations, avait accepté l'éventualité de la réalisation du résultat dommageable (<ref-ruling> consid. 5a p. 3). La jurisprudence retient également, au titre de ces circonstances extérieures, les mobiles de l'auteur et la manière dont l'acte a été commis (<ref-ruling> consid. 3c p. 252).
2.2 Selon les constatations cantonales, le recourant a reçu, de la section « main-d'oeuvre étrangère » du SPoMi, une décision du 1er juin 2006 permettant l'engagement de B._ dès l'obtention de son autorisation de séjour. Le recourant a employé le prénommé en qualité de ferrailleur une première fois du 5 au 30 juin 2006, puis une seconde fois du 30 octobre au 3 novembre 2006.
La Cour d'appel a jugé qu'on ne pouvait reprocher au recourant d'avoir, par dol éventuel, profité indûment des services de B._ du 5 au 30 juin 2006. Elle a constaté que la décision du SPoMi précisait certes que B._ ne pouvait être engagé que dès l'obtention de son autorisation de séjour, mais qu'un des collaborateurs du SPoMI avait toutefois confirmé au recourant, par voie téléphonique, que l'autorisation du prénommé allait suivre et que celui-ci pouvait déjà commencer à travailler.
En revanche, la Cour d'appel a estimé que le recourant avait agi par dol éventuel en occupant B._ du 30 octobre au 3 novembre 2006. Elle a en effet constaté que l'intéressé avait été auditionné par la police le 10 octobre 2006 en relation avec les faits de juin 2006 et qu'il aurait par conséquent dû éprouver, dès cette date, des doutes sérieux quant à l'autorisation de séjour de son employé et s'assurer que ce dernier avait bien obtenu ladite autorisation, ce qu'il n'avait toutefois pas fait.
2.3 Le recourant affirme s'être soucié de l'autorisation de séjour de son employé en automne 2006. Il explique avoir appelé le mandataire de celui-ci qui lui aurait confirmé que tout était en ordre, un recours ayant été déposé contre la décision refusant à B._ une autorisation de séjour et ce recours ayant un effet suspensif.
Il ne ressort pas de l'arrêt attaqué que le recourant, qui n'établit pas ni même ne prétend l'avoir fait, se serait prévalu en instance cantonale de l'appel téléphonique échangé avec le mandataire de son employé et des explications qui lui auraient été transmises à cette occasion. L'intéressé invoque ainsi des faits nouveaux, irrecevables dans le cadre d'un recours en matière pénale au Tribunal fédéral (cf. art. 99 al. 1 et 105 al. 1 LTF).
2.4 Le recourant explique qu'on ne lui a pas indiqué, lors de son audition par la police du 10 octobre 2006, que B._ faisait l'objet d'une interdiction de travail et affirme qu'à l'issue de cet interrogatoire, il était toujours parfaitement convaincu de ne pas avoir commis la moindre faute dans ce dossier. Il soutient également que sa conviction selon laquelle il ne commettait pas de faute en faisant travailler B._ était confortée par plusieurs éléments figurant au dossier. D'une part, l'administration cantonale des contributions l'avait informé, par courrier du 28 juillet 2006, que le prénommé ne devait plus être imposé à la source, mais bénéficiait désormais du régime de taxation ordinaire (pièce n° 5 du bordereau de pièces produites à l'appui du recours cantonal). D'autre part, après qu'il eût communiqué à B._ qu'il le licenciait, il a été interpellé par le syndicat qui lui a signifié que ce licenciement n'avait pas d'effet durant l'incapacité de travail de l'employé (cf. jugement p. 5 let. d). Il a également reçu des correspondances de la SUVA qui confirmait l'incapacité de travail de ce dernier (pièces n° 13 et 14 du bordereau de pièces produites à l'appui du recours cantonal) ainsi que des décisions de la Caisse de compensation selon lesquelles il devait continuer à verser les allocations familiales à B._ (pièces n° 15 du bordereau de pièces produites à l'appui du recours cantonal).
Selon l'arrêt attaqué, le recourant a fait appel aux services de B._ du 30 octobre au 3 novembre 2006. Comme il avait été auditionné par la police le 10 octobre 2006 en relation avec les faits de juin 2006, la Cour d'appel a estimé que l'intéressé aurait dû éprouver, dès cette date, des doutes sérieux quant à l'autorisation de séjour de B._ et par conséquent s'assurer que celui-ci avait bel et bien obtenu ce document. Or, la lecture du procès-verbal d'audition du 10 octobre 2006 ne permet pas de discerner d'éléments qui auraient pu mettre à mal la conviction du recourant selon laquelle il était autorisé à employer B._ conformément à la confirmation obtenue du SPoMi par voie téléphonique au début du mois de juin 2006. En effet, selon ce procès-verbal, le policier qui l'a interrogé ne lui a pas indiqué que B._ n'avait pas le droit de travailler et que l'autorisation de séjour attendue lui aurait été refusée. Le recourant, de son côté, a expliqué à l'agent qu'il avait engagé cet employé après avoir reçu une réponse positive du SPoMi et n'avoir jamais reçu de courrier de ce service l'informant que B._ n'avait pas le droit de travailler. Le seul fait que le recourant ait été interrogé comme prévenu d'une infraction à la LSEE ne suffit pas pour conclure qu'il aurait dû éprouver des doutes sérieux quant à l'autorisation de séjour de son employé, étant donné qu'il pensait que tout était en ordre depuis juin 2006 et que le contraire ne lui a jamais été signifié.
Ainsi, l'élément retenu, à savoir l'audition du recourant par la police du 10 octobre 2006, est insuffisant pour conclure que ce dernier se serait à tout le moins accommodé du risque d'occuper un étranger sans autorisation. Par conséquent, le recours doit être admis, l'arrêt attaqué annulé et la cause renvoyée à l'autorité cantonale pour qu'elle examine si les éléments du dossier permettent de retenir le dol éventuel ou si l'intéressé doit être acquitté.
3. En conclusion, le recours doit être admis, l'arrêt attaqué annulé et la cause renvoyée à l'autorité cantonale pour nouvelle décision dans le sens des considérants. Vu l'issue du recours, il ne sera pas perçu de frais et le canton de Fribourg versera au recourant une indemnité de dépens de 3'000 fr.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis, l'arrêt attaqué annulé et la cause renvoyée à l'autorité cantonale pour nouvelle décision.
2. Il n'est pas perçu de frais judiciaires.
3. Le canton de Fribourg versera au recourant une indemnité de dépens de 3'000 fr.
4. Le présent arrêt est communiqué aux parties et au Tribunal cantonal de l'Etat de Fribourg, Cour d'appel pénal.
Lausanne, le 20 mai 2009
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: La Greffière:
Favre Bendani