Faits:
A. X._, ressortissant gambien, est entré illégalement en Suisse le 7 novembre 1995 et y a déposé une demande d'asile sous l'identité usurpée de Y._, ressortissant guinéen. Cette demande a été rejetée le 29 février 1996. Un délai de départ échéant au 30 avril 1996 lui avait été imparti. Le renvoi n'a toutefois pas pu être effectué en raison du refus de l'intéressé de collaborer à l'établissement de sa véritable identité et de rester à la disposition des autorités compétentes du canton de Berne.
Le 27 octobre 2001, l'intéressé a été mis au bénéfice d'une autorisation de séjour à la suite de son mariage avec une ressortissante suisse. Le mariage ayant été dissous un peu moins d'un an et demi plus tard, le Service de la population et des migrants du canton de Fribourg a refusé de prolonger l'autorisation de séjour et lui a ordonné de quitter le territoire dans un délai de trente jours. Le recours interjeté contre cette décision par l'intéressé a été rejeté par arrêt du Tribunal administratif du canton de Fribourg du 19 mai 2005, la décision de renvoi cantonale a été étendue à tout le territoire de la Confédération par l'Office fédéral des migrations. L'intéressé devait quitter la Suisse jusqu'au 20 septembre 2005. Entre-temps, X._ a quitté sa dernière adresse connue dans le canton de Fribourg.
En janvier 2009, il a été placé en détention pénale dans le canton de Berne pour y subir une peine privative de liberté de 90 jour pour infraction à la loi fédérale sur les étrangers.
A sa libération, par décision du 26 avril 2009 du Service de la population et des migrants du canton de Fribourg, il a été acheminé dans le canton de Fribourg et placé en détention en vue du renvoi.
B. Par arrêt du 30 avril 2009, après avoir entendu le même jour l'intéressé assisté d'une traductrice, le Tribunal cantonal du canton de Fribourg a confirmé la légalité et l'adéquation de la détention en vue du renvoi. A l'appui de son arrêt, le Tribunal cantonal a retenu en substance qu'une décision exécutoire de renvoi avait été rendue, que le fait qu'il soit père de deux enfants en Suisse n'y changeait rien, qu'il avait été condamné à plusieurs reprises pour crimes et délits, qu'il avait trompé l'autorité sur sa réelle identité et enfin qu'il n'avait entre- pris aucune démarche en vue de l'établissement de sa nationalité.
C. Agissant en langue allemande par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral l'annulation de l'arrêt rendu le 30 avril 2009 et sa mise en liberté immédiate. Il demande d'être mis au bénéfice de l'assistance judiciaire. Il se plaint de la violation de l'interdiction de l'arbitraire et de son droit d'être entendu ainsi que des art. 75 al. 1 lettre h ainsi que 76 al. 1 lettre b chiffre 3 de la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr, RS 142.20).
Par ordonnance du 3 juin 2009 du Président de la IIe Cour de droit public, il a été renoncé à percevoir une avance de frais, un échange d'écritures a été ordonné et la requête de mise en liberté immédiate refusée.
Le Service de la population et des migrants conclut au rejet du recours. Le 23 juin 2009, l'intéressé a déposé des contre-observations.
Considérant en droit:
1. 1.1 Les mémoires doivent être rédigés dans une langue officielle, indiquer les conclusions, les motifs et les moyens de preuve, et être signés (art. 42 al. 1 LTF). D'après l'art. 54 al. 1 LTF, la procédure est conduite dans l'une des langues officielles (allemand, français, italien, rumantsch grischun), en règle générale dans la langue de la décision attaquée. Si les parties utilisent une autre langue officielle, celle-ci peut être adoptée. En l'espèce le mémoire de recours a été, comme le permet l'art. 42 al. 1 LTF, rédigé en allemand, la présente décision est toutefois rendue en français, qui est la langue de la décision attaquée.
1.2 L'étranger placé en détention en vue du renvoi ou de l'expulsion au sens de la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20) a qualité pour déposer un recours en matière de droit public au Tribunal fédéral contre la décision confirmant sa détention rendue en dernière instance cantonale (cf. art. 82 ss LTF; arrêt 2C_206/2009 du 29 avril 2009 consid. 1.1). Interjeté dans le délai et la forme prévus par la loi (cf. art. 42 et 100 al. 1 LTF), le présent recours est donc en principe recevable, tant qu'il ne porte pas sur le question du renvoi lui-même (art. 83 lettre c chiffre 4 in fine LTF).
1.3 Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF). En vertu de l'art. 99 al. 1 LTF, aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente.
En l'espèce, le recourant se prévaut d'un courrier du 15 mai 2009 que lui a adressé le Service des migrations du canton de Berne relatif à une demande d'autorisation de séjour. Postérieur à l'arrêt attaqué, ce courrier est irrecevable. L'existence d'une procédure d'autorisation de séjour initiée par le recourant est par conséquent également un fait irrecevable. Il en va de même des faits qui ressortent de l'extrait du casier judiciaire daté du 4 juin 2009 qui figure au dossier du Service de la population et des migrants du canton de Fribourg.
2. Invoquant l'art. 29 al. 2 Cst., le recourant se plaint de la violation de son droit d'être entendu.
Ce droit implique pour l'autorité l'obligation de motiver sa décision; elle peut toutefois se limiter aux points essentiels pour la décision à rendre (ATF 134 I 83 consid. 4.1 p. 88). En l'espèce, c'est à bon droit que le recourant se plaint de ce que l'arrêt attaqué ne mentionne pas les délits et crimes pour lesquels il aurait été condamné à plusieurs reprises en Suisse et qui fonderaient, selon le Tribunal cantonal, l'application de l'art. 75 al. 1 lettre h LEtr et le maintien de ce dernier en détention en raison de condamnation pour crime. Il n'est, dans ces conditions, pas nécessaire d'examiner en plus si le Tribunal cantonal a également établi de manière arbitraire les faits qui tombaient sous le coup de l'art. 75 al. 1 lettre h LEtr, comme le soulève aussi le recourant en invoquant l'art. 9 Cst., ni si l'art. 75 al. 1 lettre h LTF a bien été violé. Malgré le caractère formel du droit d'être entendu, le défaut de motivation n'a pas encore pour conséquence l'admission du recours. En effet, l'arrêt attaqué repose sur des motivations alternatives, puisqu'il a également confirmé la légalité de la détention en vue du renvoi fondée sur l'art. 76 al. 1 lettre b chiffres 3 et 4 LEtr et qu'il suffit que l'une des deux motivations justifie la décision attaquée.
3. 3.1 Intitulé "Détention en vue du renvoi ou de l'expulsion", l'art. 76 al. 1 LEtr prévoit que, lorsqu'une décision de renvoi ou d'expulsion de première instance a été notifiée, l'autorité compétente peut, entre autres mesures destinées à en assurer l'exécution, mettre la personne concernée en détention (lettre b), notamment si des éléments concrets font craindre que cette personne entende se soustraire au renvoi ou à l'expulsion, en particulier parce qu'elle ne se soumet pas à son obligation de collaborer (ch. 3) ou si son comportement permet de conclure qu'elle se refuse à obtempérer aux instructions des autorités (ch. 4). Ces deux chiffres décrivent des comportements permettant de conclure à l'existence d'un risque de fuite ou de disparition (Untertauchensgefahr); ils peuvent donc être envisagés ensemble (Andreas Zünd, Kommentar Migrationsrecht, 2008, n° 6 ad art. 76 LEtr).
Selon la jurisprudence, un risque de fuite existe notamment lorsque l'étranger a déjà disparu une première fois dans la clandestinité, qu'il tente d'entraver les démarches en vue de l'exécution du renvoi en donnant des indications manifestement inexactes ou contradictoires ou encore lorsqu'il laisse clairement apparaître qu'il n'est pas disposé à retourner dans son pays d'origine. Lorsqu'il examine le risque de fuite, le juge de la détention doit établir un pronostic, en déterminant s'il existe des garanties que l'étranger prêtera son concours à l'exécution du renvoi le moment venu, c'est-à-dire lorsque les conditions en seront réunies. Il dispose pour ce faire d'une certaine marge d'appréciation, ce d'autant qu'il doit en principe entendre l'intéressé (arrêts 2C_206/2009 du 29 mars 2009, consid. 4.1; 2C_128/2009 du 30 mars 2009, consid. 3.1).
3.2 En l'espèce, le recourant fait valoir, sur un mode appellatoire, que le Service de la population et des migrants aurait eu connaissance de l'adresse à laquelle il vivait, sans affirmer ni exposer en quoi le Tribunal cantonal aurait établi de manière manifestement inexacte les faits ou en violation du droit (cf. mémoire de recours, art. 6). Il est par conséquent douteux que ces faits puissent être pris en considération. Cet point n'a pas besoin d'être tranché du moment que le recours doit de toute manière être rejeté, même en tenant compte de ces éléments.
3.3 En l'espèce, le simple fait que le recourant ait donné une adresse à des autorités en Suisse ne garantit pas encore qu'il prêtera son concours à l'exécution du renvoi le moment venu. Les faits retenus par le Tribunal cantonal montrent au contraire qu'il y a un véritable risque de disparition: le recourant a commencé par mentir sur sa véritable identité. Il a toujours refusé de collaborer à l'établissement de sa véritable identité, sinon lorsque celle-ci lui a permis de rester en Suisse par mariage. Lorsque le Tribunal administratif a rejeté le recours qu'il avait déposé contre le renouvellement de son autorisation de séjour et lui a imparti un délai pour quitter le territoire, il a disparu. Enfin, il a réitéré son refus de quitter la Suisse en audience du 30 avril 2009. A cet égard, il soutient que son refus ne constitue pas un refus de collaborer à son renvoi, mais la manifestation de son désir de rester en Suisse auprès de ses enfants. Quoi qu'il en soit, cette objection ne lui est d'aucun secours du moment qu'il lui est loisible d'initier une procédure d'autorisation de séjour depuis son pays d'origine en se prévalant s'il le souhaite de l'art. 8 CEDH. A supposer que l'on puisse retenir que le recourant a déjà débuté une procédure d'autorisation de séjour en Suisse (cf. consid. 1.3), un tel fait ne l'autoriserait de toute façon pas à séjourner en Suisse (cf. art. 17 al. 1 LEtr), puisqu'il ne remplit pas les conditions de l'art. 17 al. 2 LEtr.
3.4 Enfin, l'exécution du renvoi ne s'avère pas d'emblée impossible pour des raisons juridiques ou matérielles (cf. art. 80 al. 6 let. a LEtr a contrario) et devrait avoir lieu dans un délai raisonnable, comme l'a retenu à bon droit le Tribunal cantonal, ce que le recourant ne critique pas (cf. art. 76 al. 4 LEtr).
3.5 Par conséquent, en jugeant que le recourant entend se soustraire à son renvoi et que son comportement permet de conclure qu'il se refuse à obtempérer aux instructions des autorités, le Tribunal cantonal n'a pas violé le droit fédéral.
4. Le recourant soutient enfin que le Tribunal cantonal a violé les art. 8 CEDH, 10 al. 2 Cst ainsi que le principe de proportionnalité. Il fait valoir qu'il vit en Suisse depuis longtemps auprès de son ex-épouse et de ses enfants.
Dans la mesure où ils sont formulés dans le but de mettre un terme à la détention, ces griefs se confondent avec la violation de l'art. 80 al. 4 LEtr. Selon cet article, lorsqu'elle examine la décision de détention, l'autorité judiciaire tient compte de la situation familiale de la personne détenue. Cette disposition ne peut servir à remettre en cause le renvoi lui-même, mais seulement à faire obstacle à la détention en raison des conditions familiales de la personne détenue (arrêt 2C_206/2009 du 29 avril 2009 consid. 4.4; Thomas Hugi Yar, Zwangsmassnahmen in Ausländerrecht, Ausländerrecht, Bâle 2009, n ° 10.144, p. 494). Le recourant ne démontre pas en quoi sa détention aurait une influence telle sur son ex-femme et ses deux enfants que la détention devrait être levée. Le Tribunal fédéral n'en voit pas non plus.
Dans la mesure où le recourant tente par ce biais de remettre en cause la question du renvoi, ses griefs sont irrecevables, car ils ne peuvent faire l'objet de la présente procédure (cf. art. 83 lettre c chiffre 4 in fine LTF, consid.1.2 ci-dessus ; cf. aussi ATF 130 II 56 consid. 2 p. 58 ainsi que Thomas Hugi Yar, op. cit., n ° 10.85, p. 463).
Ces griefs sont rejetés dans la mesure où ils sont recevables.
5. Les considérants qui précèdent conduisent au rejet du recours dans la mesure où il est recevable.
Succombant, le recourant doit en principe supporter un émolument judiciaire (art. 66 al. 1, 1ère phrase LTF). Le recours étant dénué de chances de succès, la requête d'assistance judiciaire est rejetée (cf. art. 64 al. 1 et 2 LTF a contrario). Il n'est pas perçu de frais de justice (art. 65 al. 2 LTF).
Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. La requête d'assistance judiciaire est rejetée.
3. Il n'est pas perçu de frais judiciaires.
4. Le présent arrêt est communiqué au mandataire du recourant, au Service de la population et des migrants et à la Vice-présidente de la Ie Cour administrative du Tribunal cantonal du canton de Fribourg, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 30 juin 2009
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Müller Dubey