Even though my great-grandfather had listed himself as "na" (naturalized) on the 1930 census, I just received a letter of "no record" from the U.S. Citizenship and Immigration Service. Maybe my great-grandmother gave the information and did not know, or did not understand, or maybe they had submitted the records but never actually finalized the naturalization.
Now I need to request a certification of non-existence of a naturalzation record. Looks like I'll also need to get certified copies of the Census as well. From one of the online discussion groups, I saw that this was required:
2. if he/she never became a US citizen, you must provide a), b) and c):
a) an Official statement issued by the U.S. Citizenship and Immigration Services, specifying that he/she never became a U.S. citizen. Such document must show, as confirmation, the full name with all aliases, the date and place of birth.
b) you are also required to do an extensive search with the National Archives (www.nara.gov). The National Archives will have to provide a letter of confirmation which contains full name with all aliases, the date and place of birth.
c) census record may provide additional information relevant to your case: Immigration Records, Naturalization Records, Ship Passenger Lists, Military records, U.S. Passport applications, Voter Lists Record and other (www.census.org);
I also found this:
To check to see if someone naturalized (and I assume we're talking about the US, here), there are several routes you can use. The end-all-be-all of agencies is the USCIS <www.uscis.gov>. Once you have proof of death of the person (death certificate, obit, etc.) or the person's approval (if living), you can file a G-639 FOIA request for the C-File of the person. You'll either get a "letter of no record" if the person didn't naturalize or the person's naturalization file. The problem with the USCIS is that it takes a very long time to get a response (1+ years). An advantage is that it's free.
A faster route is the National Archives (NARA) <www.archives.gov>. You have the specify where the person lived, and for a fee, the archives will search for naturalization documents filed in federal courts with that person's name in their region (each NARA office covers a region of the country). NARA will then send you either a "letter of no record" (you must request to have them mail you a letter if nothing is found) or a copy of the naturalization documents except for the certificate of naturalization (they don't keep those). It costs $22.50 for certified documents, but they get back to you in a matter of weeks.
Since the National Archives only searches documents filed in federal court, you may also want to check the county in which the person lived to see if he/she filed in that court. The procedure, price, and timing varies. You'll have to contact the county archives directly.