My Great Grandfather Abraham moved here from Vilna Russia in early 1900's with his wife Udis Rose and two children, Arthor and Bella. They started in New York City and at some point changed the last name to Gordon. We believe the last name was something like Schmedmershman (?). How do I find out the correct spelling and when and where it was changed?
Your best bet is to find your great-grandfather's US naturalization papers, and then work backwards from there to his original immigration records (probably ship, possibly land), and hopefully back from there to vital records that survived back in the Old Country.
If you have access to Ancestry.com, either through one of their free trial weekends (which tend to come during holidays like Labor Day), or through a local library, that would be the best place to start your search. FamilySearch.org has a number of transcribed and searchable naturalization records online too. A small number are on Fold3.com, but that's a subscription site. And if he came through the New York City metropolitan area, then the indices at ItalianGen.org are great too.
Or you may just want to cut to the head of the line, so to speak, and use the US Citizenship and Immigration Service (USCIS) Genealogy records request site, here: http://www.uscis.gov/genealogy
You should first read all the FAQ's and informational work on that site, and then proceed to the Index Search Request form here: https://genealogy.uscis.dhs.gov
It will cost you at least $20 to have them start digging through their records for your family. But really, please do as much research as possible on Ancestry and FamilySearch before you go asking USCIS to try to find his file, which could take months. At the very minimum, try to find the family in the 1940, 1930, 1920, and 1910 US Federal Censuses, and note their address in each one, and give that information to USCIS, to help them narrow down the search.
Finally, please be sure to note that their hometown "Vilna, Russia" really meant "Vilna, Russian Empire", not modern-day Russia. Between roughly 1920 and 1939 it was known as "Wilno, Poland". Today, the city is Vilnius, Lithuania. So while you're searching through census records and the like, please note that you may need to specifically search for people who claimed to have been born in Russia or Poland or Lithuania.