Sachverhalt: A. Der am 1. September 1977 geborene algerische Staatsangehörige X._ reiste Anfang 1998 unter Missachtung der Einreisevorschriften und unter falscher Identität in die Schweiz ein. Das von ihm eingereichte Asylgesuch wurde am 5. Februar 1998 rechtskräftig abgewiesen. Ein Gesuch um vorläufige Aufnahme wies das Bundesamt für Migration am 28. September 2004 ab. Sämtlichen Aufforderungen zur Ausreise kam X._ nicht nach. Auch ein Rückführungsversuch nach Algerien scheiterte an seinem Widerstand. X._ wurde in der Schweiz wiederholt straffällig. In der Zeit vom 2. März 1998 bis zum 14. Dezember 2007 ergingen gegen ihn total 16 Verurteilungen zu Freiheitsstrafen von insgesamt rund 33 Monaten. Den Verurteilungen lagen zum grössten Teil Vermögensdelikte sowie Widerhandlungen gegen aufenthaltsrechtliche Bestimmungen zu Grunde. Die längste einzelne Freiheitsstrafe betrug sechs Monate; sie wurde aufgrund einer Verurteilung wegen mehrfacher Widerhandlung gegen das Ausländergesetz, begangen durch Missachtung einer Ausgrenzungsverfügung, sowie wegen Hinderung einer Amtshandlung ausgesprochen. B. Am 2. Juni 2008 heiratete X._ die Schweizerin Y._ und ersuchte danach um Erteilung einer Aufenthaltsbewilligung zum Verbleib bei der Ehefrau. Mit Verfügung vom 31. Oktober 2008 wies das Migrationsamt des Kantons Zürich das Gesuch insbesondere unter Hinweis auf die Delinquenz von X._ ab. Hiergegen rekurrierten X._ und Y._ ohne Erfolg beim Regierungsrat des Kantons Zürich. Eine daraufhin beim Verwaltungsgericht des Kantons Zürich eingereichte Beschwerde wurde von diesem mit Urteil vom 17. März 2010 abgewiesen. C. Mit Eingabe vom 11. Mai 2010 führen X._ und Y._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht. Sie beantragen im Wesentlichen die Aufhebung des vorinstanzlichen Entscheids und die Erteilung einer Aufenthaltsbewilligung für X._. Das Verwaltungsgericht des Kantons Zürich sowie das Bundesamt für Migration schliessen auf Abweisung der Beschwerde. Mit Verfügung vom 18. Mai 2010 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt. Ein Gesuch von X._ und Y._ um Sistierung des bundesgerichtlichen Verfahrens wurde dagegen mit Präsidialverfügung vom 27. September 2010 abgelehnt. Die II. öffentlich-rechtliche Abteilung des Bundesgerichts hat die Angelegenheit am 15. April 2011 an einer öffentlichen Sitzung beraten.