Sachverhalt:
A. A.a X._ (geb. 1960) stammt aus Nigeria. Er heiratete hier nach einem erfolglosen Asylverfahren die um 18 Jahre ältere Schweizerin Y._. Gestützt hierauf erhielt er eine Aufenthaltsbewilligung. Am 6. Juli 1998 wurde er erleichtert eingebürgert. Am 14. September 1999 ist die Ehe X._ und Y._ geschieden worden, worauf X._ am 3. August 2000 die nigerianische Mutter seines am 2. November 1998 geborenen Sohnes heiratete, die in der Folge beide zu ihm in die Schweiz zogen. Am 16. Juli 2002 kam die gemeinsame Tochter A._ zur Welt. Am 9. Mai 2003 erklärte das zuständige Bundesamt die erleichterte Einbürgerung von X._ für nichtig, womit auch das Schweizer Bürgerrecht des Sohnes entfiel.
A.b Am 3. Oktober 2003 wies das Ausländeramt des Kantons Schaffhausen X._ und seine beiden Kinder aus der Schweiz weg. Gleichzeitig verweigerte es seiner Ehefrau die Verlängerung der Aufenthaltsbewilligung. Mit Urteil vom 14. November 2005 bestätigte das Bundesgericht letztinstanzlich diese Anordnungen: Die Beziehung X._ und Y._ sei eine Scheinehe gewesen bzw. vor der Einbürgerung von X._ definitiv gescheitert gewesen, da er bereits damals eine aussereheliche Beziehung mit seiner künftigen Ehefrau unterhalten habe. Da keines der Familienmitglieder ein festes Anwesenheitsrecht in der Schweiz besitze und die ganze Familie gemeinsam das Land verlassen müsse, liege kein Eingriff in den Schutzbereich der Garantie auf Achtung des Familienlebens (Art. 8 EMRK) vor.
B. B.a Die Familie X._ wurde in der Folge wiederholt aufgefordert, das Land zu verlassen. Sämtliche Bemühungen der Migrationsbehörden, von der nigerianischen Botschaft die notwendigen Reisepapiere für eine Ausschaffung zu erhalten, scheiterten daran, dass X._ sich konsequent weigerte, das Land zu verlassen. Er wurde deshalb erstmals am 27. September 2010 in Durchsetzungshaft genommen, welche auf Beschwerde hin vom Bundesgericht aus formellen Gründen mit Urteil vom 24. Dezember 2010 aufgehoben wurde. Am 16. Januar 2011 wurde X._ erneut in Durchsetzungshaft genommen und im Rahmen von Haftprüfungen wurde die Rechtsmässigkeit der Aufrechterhaltung der Durchsetzungskraft bis - schliesslich - 16. Juni 2011 bestätigt, zuletzt mit Entscheid des Kantonsgerichts Schaffhausen vom 12. April 2011.
B.b X._ beschwerte sich dagegen am 2. Mai 2011 beim Obergericht des Kantons Schaffhausen, welches die Beschwerde mit Entscheid vom 20. Mai 2011 abwies.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 26. Mai 2011 beantragt X._, den Entscheid des Obergerichts vom 20. Mai 2011 aufzuheben, die Rechtmässigkeit der Verlängerung der Durchsetzungshaft nicht zu bestätigen und ihn aus der Durchsetzungshaft zu entlassen. Das Migrationsamt, das Kantonsgericht und das Obergericht des Kantons Schaffhausen verzichten auf eine Vernehmlassung. Das Bundesamt für Migration hat innert Frist nicht Stellung genommen.

Erwägungen:
1. Das Bundesgericht hat bereits in seinem Urteil 2C_936/2010 vom 24. Dezember 2010 betreffend die Durchsetzungshaft gegenüber dem heutigen Beschwerdeführer, der im Übrigen bereits damals vom gleichen Anwalt vertreten war, den Zweck und die gesetzlichen Voraussetzungen der Durchsetzungshaft dargelegt und ausgeführt, wie die Überprüfung der Geeignetheit bzw. Erforderlichkeit und der Verhältnismässigkeit im Einzelfall zu erfolgen habe (a.a.O. E. 1). Es kann deshalb auf die dortigen Ausführungen verwiesen werden.
2. 2.1 Das Bundesgericht hat sodann im damaligen Urteil festgehalten, der Beschwerdeführer bestreite nicht, mit seiner Familie rechtskräftig aus der Schweiz weggewiesen worden zu sein, seine Ausreisepflicht wiederholt missachtet zu haben und nicht in Ausschaffungshaft genommen werden zu können, weil die nigerianischen Behörden sich weigern, ihn gegen seinen Willen zurückzunehmen. Unbestrittenermassen weigere er sich auch nach wie vor, mit seiner Familie die Rückreise in die gemeinsame Heimat anzutreten. Er bestreite indessen die Verhältnismässigkeit seiner Festhaltung. Diese sei mit Blick auf seine familiären Verhältnisse und seine hier eingeschulten Kinder, welche kein Wort Ibo sprächen, ungeeignet, ihn dazu zu bewegen, das Land zu verlassen.
An den damals festgestellten Umständen hat sich nach den unbestrittenen Feststellungen der Vorinstanz nichts geändert.
2.2 Nach der Rechtsprechung ist bei der Durchsetzungshaft gemäss Art. 78 AuG das mutmasslich künftige Verhalten des Betroffenen jeweils aufgrund sämtlicher Umstände abzuschätzen; dabei bildet ein erklärt unkooperatives Verhalten - wie es der Beschwerdeführer an den Tag legt und unumwunden zugesteht - einen gewichtigen Gesichtspunkt. Die Durchsetzungshaft soll den Betroffenen zwangsweise dazu veranlassen, seine Position zu überdenken (Urteil 2C_936/2010 vom 24. Dezember 2010 E. 2.1).
Der Beschwerdeführer macht geltend, er befinde sich mittlerweile insgesamt über sieben Monate in Durchsetzungshaft und habe während der ganzen Dauer des Verfahrens nicht das geringste Zeichen gegeben, wonach er sich eine Rückkehr nach Nigeria überlegen würde. Entgegen seiner Meinung, kann daraus jedoch nicht abgeleitet werden, dass es an der minimalen Wahrscheinlichkeit der Eignung der Massnahme fehlt. Die Durchsetzungshaft hat den Charakter einer Beugehaft und ist als Instrument zur Erzwingung einer durch das Gesetz vorgeschriebenen Verpflichtung im Rahmen des Ausweisungsverfahrens zu verstehen. Die maximale Haftdauer von sechs Monaten (Art. 79 Abs. 1 AuG) kann mit Zustimmung der kantonalen richterlichen Behörde um 12 Monate verlängert werden, wenn der betroffene Ausländer nicht mit der zuständigen Behörde kooperiert (vgl. Art. 78 Abs. 2 in Verbindung mit Art. 79 Abs. 2 lit. a AuG). Diese zulässige Haftdauer ist vorliegend noch nicht erreicht und es kann keineswegs ausgeschlossen werden, dass der Beschwerdeführer durch die Haft doch noch bewegt werden kann, seine Position zu überdenken. Wenn er ausführt, er werde jederzeit einen Gefängnisaufenthalt einer Rückreise unter Zurücklassung der Familie vorziehen, so übersieht er offensichtlich, dass gemäss rechtskräftigem, letztinstanzlich durch das Bundesgericht bestätigtem Entscheid nicht bloss er, sondern seine ganze Familie die Schweiz zu verlassen hat. Offenbar scheint ihm dies noch zu wenig bewusst zu sein, wenn er geltend macht, er sehe mit seiner Familie die weitere Zukunft in der Schweiz. Die Vorinstanz hat sodann - gestützt darauf, dass die Durchsetzungshaft gerade erst dann in Betracht fällt, wenn aufgrund des persönlichen Verhaltens der ausreisepflichtigen Person die Weg- beziehungsweise Ausweisung nicht vollzogen werden kann - zu Recht ausgeführt, die Anordnung beziehungsweise Verlängerung der Durchsetzungshaft sei nicht schon alleine deswegen ungeeignet, weil sich der Beschwerdeführer weigere, aktiv an seiner Ausreise mitzuwirken. Die Vorbringen des Beschwerdeführers vermögen an der zutreffenden Einschätzung der Vorinstanz, auf welche verwiesen werden kann, nichts zu ändern. Insbesondere geht sein appellatorisch vorgebrachter Verweis auf mit seiner vierköpfigen in der Schweiz lebenden Familie neu entstandene Realitäten fehl, hat doch bereits die Vorinstanz diesbezüglich zur Recht darauf hingewiesen, dass es der Beschwerdeführer selber ist, der diese Situation herbeiführte, indem er jahrelang eine freiwillige Ausreise verweigerte und seine ausländerrechtlichen Pflichten konsequent missachtete.
2.3 Nach dem Dargelegten ist es nicht bundesrechtswidrig, wenn die Vorinstanz zum Ergebnis gelangt, die Voraussetzungen für die Durchsetzungshaft seien nach wie vor gegeben. Ergänzend wird auf die ausführlichen Erwägungen im angefochtenen Entscheid verwiesen.
3. Die Beschwerde erweist sich als offensichtlich unbegründet und kann daher im vereinfachten Verfahren nach <ref-law> abgewiesen werden. Der Beschwerdeführer würde damit kostenpflichtig. Mit Blick auf seine Einkommens- und Vermögensverhältnisse ist allerdings auf die Erhebung von Kosten zu verzichten (vgl. Art. 65 f. BGG). Seinem Gesuch um unentgeltliche Rechtspflege und Verbeiständung kann indessen wegen Aussichtslosigkeit seines Begehrens nicht entsprochen werden (vgl. <ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Es werden keine Gerichtskosten erhoben.
3. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
4. Dieses Urteil wird dem Beschwerdeführer, dem Migrationsamt des Kantons Schaffhausen, dem Kantonsgericht des Kantons Schaffhausen, dem Obergericht des Kantons Schaffhausen und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 15. Juni 2011
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Zünd Dubs