Sachverhalt: A. Der serbische Staatsangehörige Y._ (geb. 10. Oktober 1963) kam 1970 erstmals in die Schweiz. In der Folge war er in Zürich angemeldet, lebte allerdings während mehreren Jahren im damaligen Jugoslawien bei seinen Grosseltern und verbrachte nur die Ferien bei seinen Eltern in der Schweiz. Erst 1980 reiste er definitiv ein und erhielt eine Niederlassungsbewilligung. Am 25. Juni 1987 wurde er vom Obergericht des Kantons Zürich wegen bandenmässigen Raubs, Versuchs dazu, Raubs sowie Raubversuchs zu dreissig Monaten Zuchthaus und zu zehn Jahren Landesverweis verurteilt. Wegen fortgesetzten Raubs und Versuchs dazu fällte das Obergericht des Kantons Zürich mit Urteil vom 11. Januar 1989 eine Zusatzstrafe von zehn Monaten Gefängnis unbedingt. Im Jahre 1991 wurde er unter dem Namen Y._ aus der Schweiz ausgeschafft. B. Ungefähr ab 1992 führte er den neuen Namen Y.A._. Im gleichen Jahr heiratete er die in der Schweiz niedergelassene Landsfrau Z.B._ und nahm in der Folge deren Namen an. Am 7. Februar 1993 reiste er unter dem Namen Y.B._ wieder in die Schweiz ein, wo ihm gestützt auf die Heirat im Kanton Solothurn eine Aufenthaltsbewilligung erteilt wurde. 1994 zogen die Ehegatten mit der inzwischen geborenen Tochter nach Zürich, wo in der Folge ein zweites Kind geboren wurde. Mit Urteil des Obergerichts des Kantons Zürich vom 2. Dezember 1999 wurde die Ehe von Z.B._ und Y.B._ geschieden. Am 11. Dezember 1996 wurde Y.B._ verhaftet. Im Rahmen der polizeilichen Abklärungen stellte sich heraus, dass Y.B._ und Y._ dieselbe Person sind und dass der Betroffene unter dem Namen Y._ bereits für die Dauer von zehn Jahren des Landes verwiesen worden war. Mit Urteil vom 11. März 1999 wurde Y.B._ vom Geschworenengericht des Kantons Zürich der mehrfach versuchten vorsätzlichen Tötung, des Verweisungsbruchs sowie des verbotenen Waffentragens schuldig gesprochen und zu elf Jahren Zuchthaus sowie lebenslänglichem Landesverweis verurteilt. Nachdem dieses Urteil auf kantonale Nichtigkeitsbeschwerde hin aufgehoben worden war, bestrafte ihn das Geschworenengericht mit Urteil vom 4. Juli 2001 mit zehn Jahren Zuchthaus und lebenslänglichem Landesverweis. Y.B._ wurde am 27. Oktober 2005 nach Belgrad ausgeschafft. Bereits am 12. Oktober 2005 verfügte das Bundesamt für Migration eine Einreisesperre auf unbestimmte Dauer. C. Im Januar 2007 heiratete Y._ (alias Y.B._) in Belgrad die Schweizer Bürgerin X._, die er während des Strafvollzuges kennengelernt hatte. Am 19. März 2008 stellte X._ ein Familiennachzugsgesuch für ihren Ehemann. Die Abteilung für Ausländerfragen des Departements des Innern des Kantons Solothurn wies das Gesuch mit Verfügung vom 15. April 2009 ab. Dagegen beschwerte sich X._ ohne Erfolg beim Verwaltungsgericht des Kantons Solothurn. D. Mit Eingaben vom 18. Juli 2009 bzw. vom 19. Juli 2009 haben X._ und Y._ "Rekurs" an das Bundesgericht erhoben mit dem sinngemässen Antrag, das Urteil des Verwaltungsgerichts des Kantons Solothurn aufzuheben und den Familiennachzug zu gewähren. Das Bundesgericht hat die kantonalen Akten beigezogen, aber keine Vernehmlassungen eingeholt.