Faits:
A. X._, né en 1976, originaire du Brésil, séjourne et travaille sans autorisation en Suisse depuis plusieurs années.
Le 27 avril 2007, l'Office cantonal de la population a prononcé à l'encontre de l'intéressé une décision de renvoi de Suisse, en application de l'art. 12 de loi fédérale sur le séjour et l'établissement des étrangers du 26 mars 1931 (LSEE; RS 1 113) et lui a imparti un délai au 30 juin 2007 pour quitter le territoire de la Confédération.
Le 20 décembre 2007, X._ a été refoulé à destination de Rio de Janeiro par les services de police.
B. Le 22 mai 2008, de retour à Genève, l'intéressé a sollicité une autorisation de séjour pour conclure un partenariat enregistré avec Y._. Le 2 décembre 2008, X._ a été interpellé par la police après avoir vendu une dose d'héroïne et déclaré être consommateur d'héroïne. Le 5 décembre 2008, l'Office cantonal de la population a refusé de lui délivrer une autorisation de séjour et lui a imparti un délai au 15 janvier 2009 pour quitter la Suisse.
Le 10 mars 2009, l'Office cantonal de la population a chargé la police d'exécuter le renvoi de l'intéressé à destination du Brésil. Le 24 août 2009, le Commissaire de police a ordonné la mise en détention administrative de l'intéressé pour un mois. Le refoulement prévu le 25 août 2009 à destination du Brésil a échoué, l'intéressé s'étant opposé à l'exécution de celui-ci.
Le 22 septembre 2009, l'Office fédéral des migrations a prononcé une mesure d'interdiction d'entrée en Suisse à l'encontre de X._, valable jusqu'au 21 septembre 2014, qui lui a été notifiée le 24 septembre 2009. Ayant vécu en France, il a été réadmis par les autorités françaises. Le 17 novembre 2009, il a été interpellé à Genève. Prévenu d'infraction à l'art. 115 de la loi fédérale sur les étrangers du 16 décembre 2005 (LEtr; RS 142.20), il a été relaxé et refoulé sur la France. Il en a été de même les 2 et 3 décembre 2009. Le 10 mars 2010, il a une nouvelle fois été interpellé par la police genevoise pour une affaire de stupéfiants. Le 11 mars 2010, il a été prévenu d'infractions aux art. 19 de la loi fédérale sur les stupéfiants et les substances psychotropes du 3 octobre 1951 (LStup; RS 812.121) et 115 LEtr, puis condamné par le juge d'instruction le 11 mars 2010 à une peine privative de liberté de trente jours pour ces mêmes infractions. Le 8 avril 2010, il a été libéré et remis à la police. Le même jour, l'Office cantonal de la population a prononcé à son encontre une décision de renvoi de Suisse, exécutoire nonobstant recours, et la police a été chargée d'exécuter sans délai ledit renvoi.
C. Le 8 avril 2010, le Commissaire de police a prononcé un ordre de mise en détention administrative à l'encontre de l'intéressé pour trois mois, soit jusqu'au 10 juillet 2010.
Par décision du 12 avril 2010, la Commission cantonale de recours en matière administrative a confirmé l'ordre de mise en détention administrative du 8 avril 2010.
Le 20 avril 2010, X._, assisté d'un avocat commis d'office, a recouru contre cette décision auprès du Tribunal administratif du canton de Genève en concluant à l'annulation de cette décision et à sa libération immédiate.
D. Par arrêt du 30 avril 2010, le Tribunal administratif a rejeté le recours. A l'appui de son arrêt, le Tribunal administratif a jugé que les conditions pour le prononcé d'une mise en détention administrative au sens de l'art. 76 al. 1 let. b ch. 2 et 3 LEtr étaient remplies. Il a aussi jugé que le renvoi était possible. En effet, le traitement à la méthadone n'était pas un traitement nécessaire et vital et aucun certificat médical n'établissait que la cure était suivie de manière sérieuse et régulière, de sorte que rien n'empêchait son interruption tandis que les soins que nécessiterait l'épilepsie n'étaient pas même allégués. L'obtention d'un laissez-passer pour le Brésil devait être rapide puisque l'intéressé y avait déjà été renvoyé et qu'il en détenait la nationalité. En particulier, une reprise des vols spéciaux dans le courant du mois de mai 2010, après leur suspension provisoire le 21 avril 2010, paraissait très réaliste. Le maintien en détention était proportionné à la situation.
E. Agissant par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'arrêt rendu le 30 avril 2010 par le Tribunal administratif, la décision rendue le 12 avril 2010 par la Commission de recours en matière administrative ainsi que l'ordre de mise en détention prononcé le 8 avril 2010 et d'ordonner sa libération immédiate. Il se plaint d'arbitraire dans l'application [recte: dans l'établissement] des faits et de la violation de l'art. 80 al. 6 let. a LEtr. Il sollicite l'octroi de l'assistance judiciaire.
Le Tribunal administratif se réfère aux considérants de l'arrêt attaqué. L'Etat-major de la police du canton de Genève propose le rejet du recours. L'intéressé a déposé des contre-observations. Bien que dûment invité à déposer des observations sur recours, l'Office fédéral des migrations n'a pris aucune position.

Considérant en droit:
1. La voie du recours en matière de droit public (<ref-law>) est en principe ouverte à l'encontre des décisions cantonales en matière de mesures de contrainte (<ref-ruling> consid. 2). Dirigé contre un arrêt rendu en cette matière par une autorité judiciaire cantonale supérieure de dernière instance (cf. art. 86 al. 1 lettre d et al. 2 LTF), le présent recours a été déposé dans le délai prévu par la loi (cf. <ref-law>) et dans les formes requises (<ref-law>).
En revanche, dans la mesure où le recourant conclut à l'annulation de la décision rendue le 12 avril 2010 par la Commission de recours en matière administrative ainsi que de l'ordre de mise en détention prononcé le 8 avril 2010, son acte est irrecevable, étant donné l'effet dévolutif du recours au Tribunal administratif (cf. <ref-ruling> consid. p. 302 s.).
2. D'après l'<ref-law>, 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. Le recourant fait référence à la communication de l'Office fédéral des migrations du 21 mai 2010, qui est postérieure à l'arrêt rendu le 30 avril 2010. Ce fait, nouveau, est par conséquent irrecevable. Il n'y a par conséquent pas lieu d'examiner le grief d'arbitraire dans l'établissement des faits qui a précisément trait à cette communication.
3. D'après l'art. 76 al. 1 let. b ch. 3 et 4 LEtr, lorsqu'une décision de renvoi a été notifiée, l'autorité compétente peut, afin d'en assurer l'exécution, mettre en détention la personne concernée si des éléments concrets font craindre que celle-ci entende se soustraire au renvoi, en particulier parce qu'elle ne se soumet pas à son obligation de collaborer, ou si son comportement permet de conclure qu'elle se refuse à obtempérer aux instructions des autorités.
En l'espèce, il ressort des constatations cantonales que le recourant remplit les conditions pour une mise en détention en application de l'art. 76 al. 1 let. b ch. 3 et 4 LEtr, ce qui n'est du reste pas contesté. Reste le point de savoir si les conditions pour maintenir la détention sont réunies.
4. 4.1 Selon l'art. 76 al. 3, 1ère, phr. LEtr, la durée de la détention visée notamment à l'al. 1 let. b ch. 3 et 4 ne peut excéder trois mois; si des obstacles particuliers s'opposent à l'exécution du renvoi ou de l'expulsion, la détention peut, avec l'accord de l'autorité judiciaire cantonale, être prolongée de quinze mois au plus. Selon l'art. 80 al. 6 let. a LEtr, la détention doit en revanche être levée notamment lorsque l'exécution du renvoi ou de l'expulsion est impossible pour des raisons juridiques ou matérielles, respectivement la prolongation refusée. Ces raisons doivent être importantes ("triftige Gründe"; ANDREAS ZÜND, Migrationsrecht, 2e éd., 2009, no 8 ad art. 80 LEtr; THOMAS HUGI YAR, Zwangs-massnahmen im Ausländerrecht, in Ausländerrecht, 2009, n° 10.111 p. 476). Ainsi, l'exécution du renvoi doit être qualifiée d'impossible lorsque le rapatriement est pratiquement exclu, même si l'identité et la nationalité de l'étranger sont connues et que les papiers voulus peuvent être obtenus. Tel est par exemple le cas si le déplacement de la personne concernée n'est pas concevable pour des raisons de santé ou qu'un Etat refuse de reprendre certains de ses ressortissants (cf. <ref-ruling> consid. 2 p. 220). Il ne suffit pas que l'exécution du renvoi soit momentanément impossible (par exemple faute de papiers d'identité), tout en restant envisageable dans un délai prévisible (cf. Zünd, op. cit., no 1 ad art. 76 LEtr; arrêt 2C_256/2008 du 4 avril 2008 consid. 7.1). En tous les cas, la durée de la détention, envisagée dans son ensemble, doit apparaître proportionnée (<ref-ruling> consid. 2.2 p. 100; <ref-ruling> consid. 1 p. 58).
4.2 La suspension des vols spéciaux à partir du 18 mars 2010 a rendu l'exécution du renvoi du recourant impossible. En effet, quand bien même cette impossibilité devrait être momentanée, elle ne saurait échapper pour autant à l'art. 80 al. 6 let. a LEtr, du moment que le renvoi n'était pas envisageable dans un délai prévisible en date du 30 avril 2010. Dans ces conditions, en confirmant le maintien en détention du recourant, le Tribunal administratif a violé le droit fédéral. Il s'ensuit que le recourant doit être remis en liberté. Le recours est admis sous cet angle.
4.3 Rien n'empêche toutefois les autorités cantonales de procéder à un nouvel examen à bref délai de la situation actuelle, notamment de prendre des renseignements sur la réalité de la reprise des vols spéciaux à destination du Brésil auprès de l'Office fédéral des migrations et de réexaminer la possibilité d'une nouvelle mise en détention en vue du renvoi, dont le prononcé, en l'espèce, correspondra assurément à l'intérêt public.
5. Les considérants qui précèdent conduisent à l'admission du recours dans la mesure où il est recevable. L'arrêt rendu le 30 avril 2010 par le Tribunal administratif est annulé et la libération du recourant prononcée.
Bien qu'il succombe, le canton de Genève n'a pas à supporter de frais judiciaires (cf. <ref-law>); en revanche, il convient de mettre à sa charge les dépens alloués au recourant, qui obtient gain de cause (cf. <ref-law>). Dans ces circonstances, la demande d'assistance judiciaire devient sans objet.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis dans la mesure où il est recevable.
2. L'arrêt rendu le 30 avril 2010 par le Tribunal administratif est annulé.
3. Le recourant est immédiatement libéré.
4. La demande d'assistance judiciaire est sans objet.
5. Le canton de Genève versera au recourant une indemnité de 2'000 fr. à titre de dépens.
6. Le présent arrêt est communiqué à la mandataire du recourant, à l'Officier de police, à la Commission cantonale de recours en matière administrative et au Tribunal administratif du canton de Genève, en section, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 25 juin 2010
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Zünd Dubey