How would Charles have a Na then a A the next census?
It would be whatever he told the census taker -- or whatever the person who gave the census taker the information. If Charles didn't give the information, but his wife or one of the children, it would be whatever they said. Same with ages, country of birth, etc. Also, it is possible, but less likely, that that is what the informant, whether Charles or someone else in the family, thought they should say.
And, Ursula (Stasia, Julia) did not have any designation.
At that time in the U.S., the wife's citizenship was her husband's. She did not have to apply for U.S. citizenship because once her husband became a U.S. citizen, she automatically became one, too. The passage of the Married Women's Act in 1922, reversed this by making a woman's citizenship independent of her marital status.
I would like to find the ship they came over on and from what region in Lithuania.
As you have already discovered, not such an easy task when the spellings swing all over the place. Imagine young German or Polish clerk in Hamburg, listening to a Lithuanian who perhaps lived among Poles, give his name and then that clerk in his own inimitable handwriting jots down what he heard. Then many years later a volunteer reads that scribbled handwritten name and guesses at the spelling, perhaps not very well, and thus the name is typed (another source of error) and thus indexed. So when we now search we are not looking at the name given by that Lithuanian emigrant, but at the typed entry of a transcription of a handwritten entry by a shipping clerk. It is because of these difficulties that genealogy research is so daunting a task that only rewards the persistent.
Grandmother told me that her parents were both Lithuanian. Also, how does Charles get to be from Poland in the 1920 census? A mistake?
A bit of history. From 1795 to WWI in 1914, all the lands that we now call Poland and Lithuania and Belarus were simply areas of Russia where Poles, Lithuanians, and Belarusians lived. These areas were divided by the Czar into provinces called gubernias or governates. The boundaries of these gubernias often changed and included various ethnic peoples. So your grandmother knew what her ethnic background was because she spoke Lithuanian, observed the customs of other Lithuanians, even though she may have lived in an area populated by ethnic Poles or even though she may have grown up on a large estate owned by a "noble" or minor aristocrat who was an ethnic Pole or a Lithuanian who spoke the upper class Polish. So many ethnic Lithuanians were bi-lingual in Polish and Lithuanian. Most of them were illiterate, did not have calendars or clocks, sometimes incorporated Polish forms to their names (e.g., endings in "-wicz" became "-vic^ius" endings). Most of these folks knew only that they were subjects of the Czar of Russia or lived in an area that once was Poland, so whatever their ethnic background, they told officials that they were from "Poland" or from "Russia".
Between the end of WWI and 1922, many ethnic Lithuanian immigrants in the U.S. (and probably elsewhere) learned that Lithuania had gradually become recognized as an independent republic and so they no longer said they were from "Poland" or "Russia" but now proudly from Lithuania. Those unaware of these developments might still give their only known "nationality".