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.