Sachverhalt: A. Die mazedonische Staatsangehörige Y._ (geb. 1973) reiste am 27. Oktober 1990 in die Schweiz ein und erhielt im Rahmen des Familiennachzugs eine Niederlassungsbewilligung. Ihr Gatte X._ (geb. 1971), ebenfalls mazedonischer Staatsangehöriger, kam am 4. September 1994 in die Schweiz, wobei ihm eine Aufenthaltsbewilligung zum Verbleib bei seiner Ehefrau erteilt wurde. X._ und Y._ haben drei gemeinsame Kinder (geboren 1995, 1997 und 2002), die in die Niederlassungsbewilligung ihrer Mutter einbezogen wurden. B. Das Ausländeramt des Kantons Schaffhausen verweigerte am 15. Juli 1999 X._ die Erteilung der Niederlassungsbewilligung wegen dessen hoher Verschuldung. Am 13. Oktober 2005 sprach das Ausländeramt zudem eine Verwarnung - unter anderem wegen seiner hohen Verschuldung - gegen X._ aus. Mit Verfügung vom 21. Dezember 2007 widerrief das Ausländeramt - nach erfolgter Gewährung des rechtlichen Gehörs - die Aufenthaltsbewilligung von X._ und wies Y._ und die drei Kinder für die Dauer von fünf Jahren aus der Schweiz aus: Das Verhalten der Familie XY._ habe zu schweren Klagen Anlass gegeben; sie seien mit Blick auf ihre Schuldenwirtschaft und Fürsorgeabhängigkeit nicht willens oder fähig, sich in die hiesige Ordnung einzufügen. Der Regierungsrat des Kantons Schaffhausen bestätigte diesen Entscheid auf Beschwerde hin am 23. September 2008. Hiergegen gelangte die Familie XY._ am 16. Oktober 2008 an das Obergericht des Kantons Schaffhausen, welches am 24. Oktober 2008 zunächst ihr Gesuch um Gewährung der unentgeltlichen Prozessführung wegen Aussichtslosigkeit der Eingabe abwies. Das Bundesgericht bestätigte diesen Zwischenentscheid mit Urteil 2C_824/2008 vom 20. Februar 2009, soweit es auf die Beschwerde eintrat. Am 8. Januar 2010 wies das Obergericht die Beschwerde in der Sache ab und forderte die Beschwerdeführer auf, die Schweiz bis spätestens 8. März 2010 zu verlassen. C. Mit Eingabe vom 8. Februar 2010 erhebt die Familie XY._ Beschwerde in öffentlich-rechtlichen Angelegenheiten, eventualiter subsidiäre Verfassungsbeschwerde, beim Bundesgericht und beantragt die Aufhebung des angefochtenen Entscheids, eventualiter die Rückweisung der Sache zur Neubeurteilung an die Vorinstanz. Gerügt wird die Verletzung von Bundesrecht und Völkerrecht. Sodann ersuchen die Beschwerdeführer um Gewährung der unentgeltlichen Rechtspflege. D. Das Obergericht des Kantons Schaffhausen verzichtet auf eine Vernehmlassung. Der Regierungsrat des Kantons Schaffhausen sowie das Bundesamt für Migration beantragen die Abweisung der Beschwerde. E. Mit Verfügung vom 15. Februar 2010 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt. 