Faits:
A. Arrivé en Suisse le 11 juin 2007, X._, né en 1988, a déposé une demande d'asile comme ressortissant sénégalais. Par décision du 13 juillet 2007, l'Office fédéral des migrations n'est pas entré en matière sur sa requête et a prononcé son renvoi de Suisse. Le 25 juillet 2007, le Tribunal administratif fédéral a rejeté le recours de X._ contre cette décision.
Entré dans la clandestinité, X._ a été interpellé le 25 octobre 2007 à Genève et mis à disposition des autorités valaisannes. S'annonçant d'origine gambienne et non sénégalaise, comme déclaré précédemment, il ne disposait d'aucune pièce d'identité et n'avait entrepris aucune démarche afin d'en obtenir. Par décision du 26 octobre 2007, le Service de l'état civil et des étrangers du canton du Valais (ci-après: le Service cantonal) a mis X._ en détention pour une durée maximale de trois mois. Cette décision a été confirmée par l'arrêt du 30 octobre 2007 du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) qui a retenu que l'intéressé avait fait des déclarations quant à sa nationalité et concernant sa famille. Le 22 novembre 2007, X._, muni d'un laissez-passer émis par les autorités gambiennes, valable pour le jour du voyage, a refusé d'embarquer sur un vol à destination de la Gambie.
B. A la demande du Service cantonal, le Tribunal cantonal a prolongé la détention de X._ jusqu'au 26 avril 2008 par arrêt du 24 janvier 2008. Il a jugé que l'attitude du recourant qui avait refusé de prendre le vol du 22 novembre 2007 justifiait cette prolongation. En outre, les autorités avaient fait preuve de diligence dans le traitement de l'affaire.
Le 25 mars 2008, X._ devait prendre un vol pour Banjul via Francfort. La compagnie aérienne a toutefois refusé, le jour même du départ, de le prendre en charge, une escorte policière n'ayant été prévue que jusqu'à Francfort.
C. Le 9 avril 2008, le Service cantonal a requis une nouvelle prolongation de détention de trois mois au Tribunal cantonal. Ledit Tribunal, dans un arrêt du 25 avril 2008, a prolongé jusqu'au 26 juillet 2008 la détention de X._. Il a retenu que l'exigence d'une escorte policière jusqu'à Banjul avait surpris les autorités chargées du rapatriement, la réservation auprès de la compagnie aérienne mentionnant que l'escorte n'était prévue que jusqu'à Francfort. Un vol spécial devait être prévu pour le retour de X._ dans son pays. Le vol du mois de mai était déjà complet. Aucun vol n'était prévu en juin à cause du championnat européen de football. Il fallait attendre juillet, voire le mois d'août, ce qui était indépendant de la volonté et de la sphère d'influence des autorités suisses. X._ persistait en outre à vouloir se rendre ailleurs qu'en Afrique, bien qu'il soit dépourvu de passeport.
D. 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 du 25 avril 2008 du Tribunal cantonal et de le libérer. Il invoque le manque de diligence des autorités suisses ainsi que la violation de l'interdiction de l'arbitraire et de son droit d'être entendu. Il requiert l'assistance judiciaire "totale".
Le Service cantonal conclut au rejet du recours sous suite de frais. L'Office fédéral des migrations renvoie à la réponse du Service cantonal et conclut, implicitement, au rejet du recours. Le Tribunal cantonal a renoncé à déposer des observations.

Considérant en droit:
1. Dès lors que la demande de libération du recourant contre la prolongation de sa détention est survenue en 2008, la loi fédérale sur les étrangers du 16 décembre 2005 (LEtr; RS 142.20), qui est entrée en vigueur le 1er janvier 2008 et a abrogé la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE; RS 1 p. 113; ch. I de l'annexe à l'art. 125 LEtr), est applicable (cf. art. 126 al. 1 LEtr a contrario).
2. Selon l'<ref-law>, le recours peut être interjeté en particulier pour violation du droit fédéral (let. a), y compris le droit constitutionnel. Le Tribunal fédéral n'examine le moyen fondé sur la violation d'un droit constitutionnel que si le grief a été invoqué et motivé de manière précise (<ref-law>; <ref-ruling> consid. 2.3 p. 466).
Le Tribunal fédéral, qui est un juge du droit, fonde son raisonnement juridique sur les faits retenus par l'autorité précédente (<ref-law>), sauf s'ils ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (cf. <ref-law>). Si le recourant entend s'écarter des constatations de fait de l'autorité précédente, il doit expliquer de manière circonstanciée en quoi les conditions de l'<ref-law> seraient réalisées (<ref-ruling> consid. 6.2 p. 288) et la correction du vice susceptible d'influer sur le sort de la cause (<ref-law>).
3. 3.1 Le recourant se plaint du fait que le Tribunal cantonal a constaté à tort que l'échec de son renvoi était dû aux cocontractants des autorités suisses, soit les compagnies aériennes qui devaient le prendre en charge, sans avoir ordonné de mesures d'instruction complémentaires. Selon lui, le formulaire d'inscription établi par la police cantonale valaisanne indiquait qu'il serait accompagné de trois agents de police jusqu'à sa destination finale. Par la suite, l'autorité qui a réservé le vol a décidé de diminuer la présence des agents de police.
3.2 Le droit d'être entendu, tel qu'il est garanti par l'art. 29 al. 2 Cst., comprend le droit pour l'intéressé de prendre connaissance du dossier (<ref-ruling> consid. 2b p. 10), de s'exprimer sur les éléments pertinents avant qu'une décision ne soit prise touchant sa situation juridique, de produire des preuves pertinentes, d'obtenir qu'il soit donné suite à ses offres de preuves pertinentes, de participer à l'administration des preuves essentielles ou à tout le moins de s'exprimer sur son résultat, lorsque cela est de nature à influer sur la décision à rendre (<ref-ruling> consid. 3.2 p. 494; <ref-ruling> consid. 2c p. 578 s.; <ref-ruling> consid. 3a p. 436). Par ailleurs, cette garantie constitutionnelle n'empêche pas l'autorité de mettre un terme à l'instruction lorsque les preuves administrées lui ont permis de former sa conviction et que, procédant d'une manière non arbitraire à une appréciation anticipée des preuves qui lui sont encore proposées, elle a la certitude qu'elles ne pourraient l'amener à modifier son opinion (<ref-ruling> consid. 2.1 p. 429). En outre, l'art. 29 al. 2 Cst. ne confère pas à lui seul le droit d'être entendu oralement par l'autorité (cf. <ref-ruling> consid. 4c p. 469 en relation avec l'art. 4 aCst.).
L'art. 87 al. 1 lettre b de la loi valaisanne du 6 octobre 1976 sur la procédure et la juridiction administratives, invoqué par le recourant, n'accorde pas de droits supplémentaires à ceux figurant à l'art. 29 Cst.
3.3 Le Tribunal cantonal a effectivement retenu que la réservation de Genève à Banjul indiquait qu'il s'agissait d'un rapatriement avec escorte seulement jusqu'à Francfort et que les compagnies aériennes étaient "à l'évidence" au courant de ce fait. En outre, selon ledit Tribunal, personne ne prétendait que les compagnies aériennes avaient subordonné la réservation à une escorte jusqu'à Banjul.
L'affirmation du recourant selon laquelle, dans un premier temps, il devait être accompagné de trois agents de police jusqu'à sa destination finale est erronée. Il ressort du dossier qu'initialement le recourant devait prendre un vol pour Banjul via Casablanca et Dakar et être escorté jusqu'à Dakar. Il n'a jamais été prévu, comme le prétend le recourant, de l'escorter jusqu'à sa destination finale, soit Banjul.
Au surplus, le recourant n'établit pas en quoi l'éventuelle erreur du Tribunal cantonal sur les détails de l'escorte pouvait influencer le sort de la cause.
Au vu de ce qui précède, le Tribunal cantonal qui avait formé sa conviction n'avait pas à procéder à une instruction complémentaire afin de déterminer à qui était imputable l'échec du départ prévu le 25 mars 2008. Le droit d'être entendu de la recourante n'a pas été violé et les faits n'ont pas été établis de façon arbitraire.
4. 4.1 Le litige porte sur la décision de prolonger jusqu'au 26 juillet 2008 la détention du recourant ordonnée le 26 octobre 2007 sur la base de l'art. 13b al. 1 lettre c LSEE, soit en raison de l'existence d'indices concrets laissant craindre que l'intéressé n'ait alors cherché à se soustraire à son refoulement - en particulier le fait qu'il ne respectait pas son obligation de collaborer -. Ces motifs de détention ont été repris pratiquement tels quels à l'art. 76 al. 1 lettre b ch. 3 LEtr (cf. le message du Conseil fédéral du 8 mars 2002 concernant la loi sur les étrangers, in FF 2002 p. 3469 ss, p. 3570).
Aux termes de l'art. 76 al. 3 LEtr, si des obstacles particuliers s'opposent à l'exécution du renvoi ou de l'expulsion, la détention prononcée pour l'un des motifs visés à l'art. 76 al. 1 lettres a et b ch. 1 à 4 LEtr peut être prolongée, avec l'accord de l'autorité judiciaire cantonale, de quinze mois au plus et de neuf mois au plus pour les mineurs âgés de 15 à 18 ans. Les démarches nécessaires à l'exécution du renvoi ou de l'expulsion doivent être entreprises sans tarder (art. 76 al. 4 LEtr). Il est nécessaire, conformément à la jurisprudence rendue sous l'empire de l'ancien droit (cf. <ref-ruling> consid. 3a p. 374, 377 consid. 2a p. 379), que l'exécution du renvoi soit momentanément impossible (p.ex. faute de papiers d'identité), tout en restant envisageable dans un délai prévisible. En outre, la décision et l'examen de la détention doivent respecter les exigences (notamment formelles) fixées à l'art. 80 LEtr.
4.2 A la suite de la décision de non-entrée en matière du 13 juillet 2007, le recourant ne s'est pas présenté aux autorités chargées de son renvoi et a vécu dans la clandestinité jusqu'à son arrestation à Genève le 25 octobre 2007. Il a d'abord déclaré être sénégalais pour ensuite dire qu'il était gambien. Il n'a pas de papiers d'identité et n'a rien entrepris pour s'en procurer. Il a toujours déclaré ne pas vouloir rentrer dans son pays. En agissant de la sorte, le recourant a adopté un comportement rénitent et démontré qu'il ne respectait pas son obligation de collaborer. Il s'agit là d'éléments concrets faisant craindre qu'il ne cherche à se soustraire à son refoulement (cf. art. 76 al. 1 lettre b ch. 3 LEtr) et permettant de conclure qu'il refuse d'obtempérer aux instructions des autorités (cf. art. 76 al. 1 lettre b ch. 4 LEtr).
Le recourant a été placé en détention le 26 octobre 2007 et, le 22 novembre 2007, possibilité lui a été donnée d'être rapatrié, ce que l'intéressé a refusé. A la suite de l'obtention d'un laissez-passer, le recourant devait prendre un vol spécial à destination de Banjul le 25 mars 2008. Les circonstances décrites de manière non arbitraire dans l'arrêt attaqué ont empêché l'embarquement de l'intéressé. Contrairement à ce que soutient le recourant, on ne peut imputer l'échec de ce renvoi, et le délai supplémentaire qui en découle jusqu'au prochain départ de l'intéressé, à un manque de diligence des autorités suisses chargées du renvoi. L'intéressé pourra embarquer sur le prochain vol spécial disponible, vraisemblablement en juillet ou en août. Certes, depuis le 25 mars 2008, cette période peut paraître longue, mais selon les faits retenus, elle s'explique objectivement et pour des raisons indépendantes des autorités suisses. De toute façon, après avoir refusé en date du 22 novembre 2007 de monter à bord d'un avion, puis déclaré aux personnes qui l'accompagnaient à l'aéroport le 25 mars 2008, comme cela est mentionné au dossier, qu'il refusait toujours de rentrer en Gambie, le recourant est mal venu de se plaindre du contre-temps occasionné par le départ manqué du 25 mars 2008. Un tel comportement est contradictoire et contraire au principe de la bonne foi. On ne saurait dès lors considérer que le principe de célérité figurant à l'art. 76 al. 4 LEtr n'est pas respecté.
4.3 Au vu de ce qui précède, le Tribunal cantonal n'a pas violé le droit fédéral en prolongeant la détention du recourant pour trois mois. Il a respecté en particulier l'art. 76 al. 1 lettre b ch. 3, al. 3 et al. 4 LEtr ainsi que le principe de la proportionnalité.
5. Le recourant mentionne les art. 5 par. 1 let. f CEDH et 31 Cst. Toutefois, aucune argumentation n'est développée à suffisance de droit à cet égard (cf. consid. 2). Dès lors, son grief est irrecevable.
6. Manifestement infondé, le présent recours doit être rejeté.
Le recourant a requis le bénéfice de l'assistance judiciaire. Compte tenu de sa situation financière précaire, sa demande peut être admise (<ref-law>; concernant le droit à l'assistance judiciaire en détention cf. <ref-ruling>). Par conséquent, il y a lieu de le dispenser des frais et d'allouer une indemnité à son mandataire, désigné comme avocat d'office (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. La demande d'assistance judiciaire est admise.
3. Il n'est pas perçu de frais judiciaires.
4. La Caisse du Tribunal fédéral versera à Me Nicolas Fardel une indemnité de 1'500 fr. à titre d'avocat d'office.
5. Le présent arrêt est communiqué au mandataire du recourant, au Service de l'état civil et des étrangers et à la Cour de droit public du Tribunal cantonal du canton du Valais, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 27 juin 2008
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
T. Merkli E. Kurtoglu-Jolidon