Sachverhalt: A. A.a Der aus Palästina (Westbank) stammende X._, geb. 1969, reiste am 25. Juni 1996 in die Schweiz ein, wo er um Asyl ersuchte. Das Gesuch wurde am 11. November 1998 abgewiesen. Am 8. September 1998 wurde X._ wegen Betäubungsmitteldelikten mit 18 Monaten Gefängnis bei bedingtem Vollzug und mit einer Landesverweisung für die Dauer von sieben Jahren bestraft. Die in der Folge angeordnete Ausschaffungshaft führte nicht zum Ziel, da die Ausschaffung mangels Reisepapieren nicht vollzogen werden konnte. Der danach ergangenen Aufforderung, die Schweiz selbständig zu verlassen, kam X._ nicht nach. Am 25. Mai 2000 verurteilte ihn das Obergericht des Kantons Zürich erneut wegen Betäubungsmitteldelikten sowie wegen falschen Zeugnisses zu zehn Monaten Gefängnis unbedingt. Gleichzeitig ordnete es den Vollzug der bedingt ausgefällten Gefängnisstrafe vom 8. September 1998 an. Vom 19. September 1999 bis zum 12. November 2001 befand sich X._ zuerst in Untersuchungshaft und später im Strafvollzug. A.b Am 13. September 2002 ersuchte der Kanton Zürich das zuständige Bundesamt für Flüchtlinge (heute: Bundesamt für Migration), X._ vorläufig aufzunehmen. Das Gesuch wurde am 15. Juli 2003 abgewiesen. Eine dagegen beim Eidgenössischen Justiz- und Polizeidepartement eingereichte Beschwerde ist noch immer (seit dem 1. Januar 2007 beim Bundesverwaltungsgericht) hängig. A.c Im Mai 2007 liess sich X._ von seiner ersten in Palästina lebenden Ehefrau scheiden, und am 29. Juni 2007 heiratete er die in der Schweiz niedergelassene spanische Staatsangehörige Y._, geb. 1978. Diese Ehe blieb bisher kinderlos. X._ ist hingegen Vater von zwei in Palästina bei der Mutter lebenden Söhnen, die in den Jahren 1991 und 1993 geboren wurden. A.d Vom 1. Dezember 1997 bis zum 31. Juli 1998 arbeitete X._ als Küchenhilfe in einem Restaurant in Zürich. Nach der Entlassung aus dem Strafvollzug war er vom 7. Januar 2002 bis zum 11. Februar 2002 als Office-Mitarbeiter in einem Restaurantbetrieb und vom 11. Februar bis zum 12. März 2002, als ihm ein Arbeitsverbot auferlegt wurde, als Pizzaiolo in einem anderen Restaurant erwerbstätig. Danach war er im Rahmen des Programms "Gemeinnützige Einsatzpläne der Stadt Zürich" am Empfang der Asylorganisation der Stadt Zürich aktiv. Seit Anfang 2008 arbeitet er als Sicherheitsbeamter und Detektiv bei einer privaten Unternehmung im Sicherheitsbereich. A.e Mit Strafbefehl vom 10. März 2008 wurde X._ wegen Mitführens von Waffen und Munition ohne Waffentragbewilligung mit einer bedingten Geldstrafe von zwei Tagessätzen zu Fr. 70.-- und mit einer Busse von Fr. 300.-- bestraft. B. Mit Verfügung vom 7. September 2007 wies das Migrationsamt des Kantons Zürich ein Gesuch von X._ um Erteilung einer Aufenthaltsbewilligung EG/EFTA zum Verbleib bei seiner Ehefrau ab und setzte ihm eine Frist zum Verlassen des schweizerischen Staatsgebietes. Zur Begründung führte es im Wesentlichen aus, er sei insgesamt zu Freiheitsstrafen von 28 Monaten Dauer verurteilt worden, habe sich über Jahre hinweg seiner Ausreisepflicht widersetzt und habe sich nicht gewillt gezeigt, sich in die schweizerische Rechtsordnung einzufügen. C. Am 13. August 2008 wies der Regierungsrat des Kantons Zürich einen dagegen erhobenen Rekurs ab. Mit Urteil vom 21. Januar 2009 wies das Verwaltungsgericht des Kantons Zürich, 2. Kammer, eine dagegen eingereichte Beschwerde ab. Zur Begründung führte es im Wesentlichen aus, X._ stehe zwar gestützt auf das Freizügigkeitsrecht zwischen der Schweiz und der Europäischen Gemeinschaft und ihren Mitgliedstaaten ein Anspruch auf Bewilligung zu, doch sei deren Verweigerung zum Zwecke des Schutzes der öffentlichen Ordnung zulässig. D. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 23. März 2009 stellen X._ und Y._ in der Sache die folgenden Rechtsbegehren: "1. Der angefochtene Entscheid sei aufzuheben; 2. Der Kanton Zürich sei anzuweisen, dem Beschwerdeführer die Jahresbewilligung zu erteilen; 3. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen; 4. Subeventuell sei die Wegweisungsverfügung des Migrationsamts des Kantons Zürich vom 7.9.2007 aufzuheben; ..." Zur Begründung wird im Wesentlichen eine Verletzung des Freizügigkeitsrechts geltend gemacht. Die Staatskanzlei (für den Regierungsrat) des Kantons Zürich schliesst auf Abweisung der Beschwerde. Das Verwaltungsgericht beantragt Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Bundesamt für Migration stellt ebenfalls Antrag auf Abweisung und führt dazu aus, das Freizügigkeitsrecht vermittle X._ und Y._ keinen Anspruch auf Anwesenheitsbewilligung. E. Mit Verfügung vom 26. März 2009 erteilte der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde die aufschiebende Wirkung.