It is a widely held error that the Nuremberg Laws stripped those Germans who were defined as "Jews" of their "citizenship." Third Reich citizenship law (Staatsangehörigkeitsrecht) is a very complicated matter. If you are interested in details, I can recommend you my article in theologie.geschichte 2007 (in German, on the Web). To make it short: the Reichsbürgergesetz - one of the Nuremberg laws of 1935 - created two classes of German citizens: those with "full political rights " (whatever that might have meant in Nazi Germany), the Reichsbürger, and the non-Reichsbürger. It made "Jews" and "Gypsies" - I deliberately use scare quotes to stress that "Jew" and "Gypsy" was a political construct - second-class citizens, that is right. They remained, however, Staatsangehörige (Reich citizens). As such they were, e.g., interned in France, the UK, and Belgium at the outbreak of the war, Nazis and anti-Nazi refugees, Jewish or Gentile, alike.
I know that it is very difficult for Americans to understand this. Citizenship in your country entitles to full political rights, AFAIK with some minor exceptions, such as - please correct me if necessary - a U.S. president must be a born American.
Nick Terry (thank you, Nick!) provided us with a link to a Web page where all of you can read the original (sorry, German) text of the Reichsbürgergesetz:
http://alex.onb.ac.at/gesetze_drab_fs.htm
You can see there that Staatsangehöriger is the generic term, and Reichsbürger denotes only a subset of all Staatsangehörigen of the 3rd Reich. As the authoritative commentary by Stuckart and Globke clearly stated, Staatsangehörigkeit was not linked to "race" or "nationality," an individual not of "German or related blood" (that was the official word for "Aryan") could be a Reich Staatsangehöriger. Though a German Jewish (or Gypsy) Staatsangehöriger could not be a Reichsbürger, s/he did not become staatenlos ("stateless," if I translate this correctly) by virtue of the Reichsbürgergesetz. That is not "my interpretation," it is the text of the law. It becomes "interpretation" only when translated into a language that has no specific words for the German terms. (Translation is always interpretation - one of the fundamentals I learned when studying Theology.)
Staatsangehörigkeit is and was the only criterion for treating individuals in international relations - it was e.g. mentioned in passports and visa - and had also significant influence in inner state affairs, such as in family and inheritance law. E.g. legal residents of the Reich who had not German Staatsangehörigkeit, were not affected by the Blutschutzgesetz and its decrees. An "Aryan" Swiss merchant living in Berlin could have a love affair with an Italian Jewish girl, and nobody would care about.
The Reichsbürgergesetz - against widely held opinion in English speaking countries - itself had very little influence on everyday life in the Reich. It did not make Jewish and Gypsy Germans stateless, and the discriminations against non-Reichsbürger as mentioned in the First Decree to the Reichsbürgergesetz only repeated and summarized established customs: a non-Reichsbürger could not hold a public office (which was already law since February 1933 with the Law of the Restitution of the Civil Service - thanks to KentFord9 who remembered us of it!), and exclusion from voting had little effect in the Führer state.
BTW, legal discrimination against a subset of the Staatsangehörigen was not a Nazi invention. E.g. women acquired the right to vote in Germany not before 1918, and in Weimar times a woman in the civil service was dismissed when marrying . . .