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.