Sachverhalt:
A. Der nach eigenen Angaben aus Guinea stammende X._ (geb. 1986) durchlief im Jahre 2004 in der Schweiz erfolglos ein Asylverfahren und wurde rechtskräftig aus der Schweiz weggewiesen (Entscheid des damaligen Bundesamtes für Flüchtlinge vom 4. Februar 2004, Urteil der Schweizerischen Asylrekurskommission vom 22. März 2004). Vom 22. Juli 2004 bis zum 21. Oktober 2004 und vom 13. Februar 2007 bis zum 11. Mai 2007 befand er sich bereits zwei Mal in Ausschaffungshaft; er wurde jedoch daraus jeweils wieder entlassen, weil die Wegweisung nicht vollzogen werden konnte. Inzwischen delinquierte er und wurde wegen qualifizierter Widerhandlung gegen das Betäubungsmittelgesetz zu einer bedingten Freiheitsstrafe von 16 Monaten verurteilt.
B. Diplomatische Delegationen aus Guinea hatten X._ an Befragungen vom 13. Januar 2006 und 26. September 2008 nicht als guineischen Staatsangehörigen anerkannt. In einem "Herkunftsgespräch" mit dem Betroffenen am 5. Februar 2009 kam der zuständige Sachbearbeiter des Amtes für Migration Basel-Landschaft zwar zum Schluss, X._ stamme "zu 70 % aus Guinea, keinesfalls aber aus Gambia". Eine Woche später, an einer Befragung vom 12./13. Februar 2009, wurde der Letztere dann allerdings von einer gambischen Delegation als gambischer Staatsbürger anerkannt. Am 25. Februar 2009 verfügte das Bundesamt für Migration gegen X._ ("Staatsangehörigkeit: Gambia") ein Einreiseverbot auf unbestimmte Zeit.
C. Mit Urteil vom 3. März 2009 bestätigte der Einzelrichter für Zwangsmassnahmen im Ausländerrecht am Kantonsgericht Basel-Landschaft eine vom kantonalen Amt für Migration am 27. Februar 2009 gegenüber X._ erneut angeordnete Ausschaffungshaft bis zum 26. Mai 2009.
Am 18. März 2009 verweigerte X._ den Antritt eines für ihn gebuchten Fluges nach Gambia.
Mit Schreiben vom 18. Mai 2009 beantragte das Amt für Migration Basel-Landschaft die Verlängerung der Ausschaffungshaft. Am 26. Mai 2009 gab der Einzelrichter für Zwangsmassnahmen im Ausländerrecht am Kantonsgericht Basel-Landschaft (als Haftrichter) diesem Antrag statt und verlängerte die Haft - nach Durchführung einer mündlichen Verhandlung - bis zum 26. August 2009.
D. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 15. Juni 2009 an das Bundesgericht beantragt X._, das letztgenannte Urteil des Haftrichters aufzuheben und die sofortige Haftentlassung anzuordnen. Überdies ersucht er um unentgeltliche Rechtspflege unter Einschluss der unentgeltlichen Verbeiständung.
Das Amt für Migration Basel-Landschaft schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Kantonsgericht Basel-Landschaft hat auf eine Stellungnahme verzichtet, ebenso das Bundesamt für Migration.
Mit Eingabe vom 29. Juni 2009 hat sich X._ nochmals zur Sache geäussert.

Erwägungen:
1. Sowohl gegen den letztinstanzlichen Entscheid über die Anordnung der Ausschaffungshaft als auch gegen jeden kantonal letztinstanzlichen Entscheid über die Haftverlängerung steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten nach <ref-law> an das Bundesgericht offen. Die vorliegende Beschwerde erweist sich daher als zulässig.
2. 2.1 Die zuständige kantonale Behörde schafft Ausländer u.a. aus, wenn diese sich in Haft nach den Artikeln 76 und 77 befinden und ein rechtskräftiger Aus- oder Wegweisungsentscheid vorliegt (Art. 69 Abs. 1 lit. c AuG). Haben Ausländer die Möglichkeit, rechtmässig in mehrere Staaten auszureisen, so kann die zuständige Behörde sie in das Land ihrer Wahl ausschaffen (Art. 69 Abs. 2 AuG).
2.2 Wurde ein erstinstanzlicher Weg- oder Ausweisungsentscheid eröffnet, so kann die zuständige Behörde nach Art. 76 Abs. 1 AuG die betroffene ausländische Person zur Sicherstellung des Vollzugs bei Vorliegen bestimmter Haftgründe in Haft nehmen. Zu diesen Haftgründen zählt unter anderem, dass konkrete Anzeichen befürchten lassen, die ausländische Person wolle sich der Ausschaffung entziehen, insbesondere weil sie ihrer Mitwirkungspflicht nicht nachkommt (sog. Untertauchensgefahr; Art. 76 Abs. 1 lit. b Ziff. 3 AuG); bei einem straffälligen Ausländer ist eher als bei einem unbescholtenen davon auszugehen, er werde in Zukunft behördliche Anordnungen missachten (vgl. <ref-ruling> E. 3 S. 58 f.; <ref-ruling> E. 2a, 148 E. 2b/aa S. 152; <ref-ruling> E. 2b S. 198). Ein weiterer Haftgrund liegt darin, dass der Ausländer andere Personen ernsthaft bedroht oder an Leib und Leben erheblich gefährdet und deshalb strafrechtlich verfolgt wird oder verurteilt worden ist (Art. 76 Abs. 1 lit. b Ziff. 1 in Verbindung mit Art. 75 Abs. 1 lit. g AuG). Weiter muss sich die Haft als verhältnismässig erweisen, und der Vollzug der Weg- oder Ausweisung darf nicht aus rechtlichen oder tatsächlichen Gründen undurchführbar sein (vgl. Art. 80 Abs. 6 lit. a AuG). Auf Seiten der Behörden ist die Papierbeschaffung sodann mit dem nötigen Nachdruck zu verfolgen (Art. 76 Abs. 4 AuG). Die Haft darf höchstens drei Monate dauern; stehen dem Vollzug der Weg- oder Ausweisung besondere Hindernisse entgegen, so kann sie mit Zustimmung des Haftrichters um höchstens 15 Monate verlängert werden (Art. 76 Abs. 3 AuG).
3. 3.1 Gegen den Beschwerdeführer liegt eine Verurteilung zu einer bedingten Freiheitsstrafe von 16 Monaten wegen qualifizierter Widerhandlung gegen das Betäubungsmittelgesetz vor. Damit erweist sich der Haftgrund von Art. 76 Abs. 1 lit. b Ziff. 1 in Verbindung mit Art. 75 Abs. 1 lit. g AuG als erfüllt.
3.2 Gleiches gilt für den Haftgrund der Untertauchensgefahr (Art. 76 Abs. 1 lit. b Ziff. 3 AuG): Die Herkunft des Beschwerdeführers ist nicht restlos geklärt: Er gibt an, aus Guinea zu stammen. An der Haftrichterverhandlung vom 26. Mai 2009 machte er geltend, er habe versucht, Papiere von Guinea zu beschaffen. Zu belegen vermag er diese Behauptungen aber nicht, obwohl er sich seit über fünf Jahren in der Schweiz befindet und genügend Zeit gehabt hätte, die nötigen Vorbereitungen für eine Ausreise zu treffen (vgl. Urteil 2C_255/2009 vom 3. Juni 2009, E. 3.2). Zugleich bestehen konkrete Hinweise dafür, dass er nicht aus Guinea, sondern aus Gambia stammt. Vor dem Hintergrund der ausdrücklichen Anerkennung des Beschwerdeführers als gambischer Staatsangehöriger durch eine gambische Delegation und aufgrund des Umstandes, dass das Bundesamt für Migration ihn beim Erlass des Einreiseverbotes im Februar 2009 ebenfalls als Gambier anerkannt hatte (vorne lit. B), erhält die Feststellung des zuständigen Sachbearbeiters des kantonalen Migrationsamtes am Herkunftsgespräch, der Betroffene stamme "zu 70 % aus Guinea, keinesfalls aber aus Gambia", entsprechend geringes Gewicht. Am besagten Herkunftsgespräch hatte sich der Beschwerdeführer darüber hinaus dahingehend geäussert, dass er hier in der Schweiz seine Freundin heiraten wolle, was ebenfalls Zweifel an seinem Willen zur Ausreise weckt. Die Annahme des Haftrichters, der Beschwerdeführer unternehme - in Verletzung seiner Mitwirkungspflichten - nicht das ihm Mögliche, um seine Herkunft klarzustellen, ist deshalb nicht offensichtlich unrichtig und nicht zu beanstanden (vgl. Art. 97 und Art. 105 BGG).
3.3 Zu den besonderen Hindernissen, die nach Art. 76 Abs. 3 AuG eine Haftverlängerung zu rechtfertigen vermögen, zählen aussergewöhnliche Schwierigkeiten bei der Papierbeschaffung oder Probleme bei der Organisation der zwangsweisen Rückschaffung. Solche liegen hier vor, zumal der Beschwerdeführer nicht kooperiert und eine freiwillige Ausreise bisher verweigert hat. Unter Verhältnismässigkeitsgesichtspunkten ist weiter zu berücksichtigen, dass der Beschwerdeführer die Verzögerung der Ausreise mit zu verantworten hat. Die Behörden durften ihn mit Blick auf einen neuen ernsthaften Ausschaffungsversuch - verbunden mit der Verletzung der Mitwirkungspflichten - auch wieder in Haft nehmen (dazu Thomas Hugi Yar, § 10 Zwangsmassnahmen im Ausländerrecht, in: Uebersax/Rudin/Hugi Yar/Geiser [Hrsg.], Ausländerrecht, 2. Aufl., 2009, Rz. 10.158 ff.).
3.4 Der Beschwerdeführer macht geltend, der Vollzug seiner Wegweisung sei zur Zeit aus rechtlichen und tatsächlichen Gründen undurchführbar. Der Vollzug werde erst dann möglich sein, wenn die Behörden von Guinea die Staatsbürgerschaft ihres eigenen Bürgers endlich anerkennen würden.
Damit stösst der Beschwerdeführer ins Leere: Die Frage seiner Herkunft bildet nicht Gegenstand des Haftprüfungsverfahrens (Urteil 2C_192 /2009 vom 27. März 2009, E. 2.4 mit Hinweis auf <ref-ruling> E. 2.2. S. 197 f.), und er scheint mit seiner Argumentation zu verkennen, dass er in der Schweiz über kein Anwesenheitsrecht verfügt und das Land verlassen muss.
Allein der Umstand, dass sich eine Ausreise nur schwer organisieren lässt, macht die Ausschaffung nicht undurchführbar im Sinne von Art. 80 Abs. 5 AuG. Die Haft ist nur dann unzulässig, wenn keine oder bloss eine höchst unwahrscheinliche, rein theoretische Möglichkeit besteht, die Wegweisung zu vollziehen, nicht indessen bei einer ernsthaften, wenn auch allenfalls noch geringen Aussicht hierauf (<ref-ruling> E. 4 S. 59 ff.).
Vorliegend ist eine Ausschaffung des Beschwerdeführers nach Gambia möglich und absehbar (Ziff. 8 des angefochtenen Entscheides). Der Sonderflug ist beantragt (vgl. Protokoll der Haftrichterverhandlung vom 26. Mai 2009) und "im August" vorgesehen; es liegt damit auch keine Verletzung des Beschleunigungsgebotes vor. Die Möglichkeit, im Sinne von Art. 69 Abs. 2 AuG rechtmässig in ein anderes Land auszureisen, vermochte der Beschwerdeführer nicht aufzuzeigen. Ist aber eine Ausreisemöglichkeit gegeben, ist der Behörde nicht zuzumuten, weitere Abklärungen für eine andere Destination zu treffen (Andreas Zünd, in: Spescha/Thür/Zünd/Bolzli, Kommentar Migrationsrecht, Zürich 2008, N 7 zu Art. 69 AuG).
Der Beschwerdeführer hat es weiterhin in der Hand, sich ein gültiges Reisepapier für Guinea zu beschaffen, wie er dies angekündigt hat (vgl. Vernehmlassung des Migrationsamtes, S. 2). Gelingt ihm dies, kann sein Wunsch zur rechtmässigen Ausreise dorthin im Rahmen des Vollzugs der Wegweisung noch berücksichtigt werden (E. 2.1, am Ende).
4. 4.1 Die Beschwerde erweist sich damit als unbegründet und ist abzuweisen.
4.2 Der Beschwerdeführer stellt ein Gesuch um unentgeltliche Rechtspflege und Verbeiständung. Nach <ref-law> wird dies bei Bedürftigkeit gewährt, sofern die Rechtsbegehren nicht aussichtslos erscheinen. Gemäss der bundesgerichtlichen Rechtsprechung darf einem bedürftigen Häftling im Haftverlängerungsverfahren nach drei Monaten der unentgeltliche Rechtsbeistand grundsätzlich nicht verweigert werden (<ref-ruling> E. 3.2 S. 99 ff.; <ref-ruling> E. 3b S. 276 ff.; Hugi Yar, a.a.O., Rz. 10.41). Diese Rechtsprechung gilt allerdings für die haftrichterliche Überprüfung des Haftentscheids und setzt an sich ein entsprechendes Gesuch des Häftlings vor dem Haftrichter voraus. Sie gilt nicht ohne weiteres auch für eine richterliche Rechtsmittelinstanz, namentlich für das Bundesgericht.
Im vorliegenden Fall konnte der Beschwerdeführer nicht ernsthaft mit einer Gutheissung seiner Anträge rechnen, zumal der angefochtene Entscheid im Einklang mit der bundesgerichtlichen Rechtsprechung zur Verlängerung der ausländerrechtlichen Administrativhaft steht. Darüber hinaus kann nicht gesagt werden, der Beschwerdeführer sei im Verfahren der haftrichterlichen Überprüfung des Haftverlängerungsentscheides nicht anwaltlich vertreten gewesen: Das Kantonsgericht Basel-Landschaft hatte die Vorladung zum Haftprüfungstermin vom 26. Mai 2009 am 19. Mai 2009 u.a. auch an den Rechtsvertreter des Beschwerdeführers versandt. Rechtsanwalt Suter teilte dem Kantonsgericht indessen fast eine Woche später - am 25. Mai 2009 - mit, er sei "aus terminlichen Gründen nicht in der Lage, an der Verhandlung teilzunehmen". Diese Verhandlung fand in der Folge dann ohne ihn statt (vgl. das entsprechende Protokoll).
Unter den genannten Umständen dringt der Beschwerdeführer mit seiner Argumentation, es sei vorliegend "erstmals vor Bundesgericht eine anwaltliche Vertretung durchgeführt" worden (vgl. Ziff. 13 der Beschwerdeschrift) nicht durch; er muss sich das Verhalten seines Rechtsvertreters im kantonalen Verfahren anrechnen lassen.
Dies führt auch zur Abweisung des Gesuchs um unentgeltliche Rechtspflege und Verbeiständung. Hingegen rechtfertigt es sich, keine Kosten zu erheben (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3. Es werden keine Gerichtskosten erhoben.
4. Dieses Urteil wird dem Beschwerdeführer, dem Amt für Migration und dem Kantonsgericht Basel-Landschaft, Einzelrichter für Zwangsmassnahmen im Ausländerrecht, sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 6. Juli 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Klopfenstein