I am trying to help out a cousin of mine who is doing research into her mothers side of the family (not my relative). She is trying to find out what her great-great-grandfathers last name was before he changed it. She said he came to America around 1891 and changed the name around 1900-1910 to Becker. She said she can find him (and pretty sure it is the right one) on the 1910 census (with the Becker name). She is trying to find immigration papers, but since she does not know what the name was, that is tough. Is there somewhere to begin looking if someone changed their name?
You did not mention the state, but state censuses such as the NY state 1905 census may allow you to narrow the time frame down.
State would probably be Maryland. Even finding out he is in the census (1900 or 1910) with the name of Becker still does not say what is was changed from. Knowing the name it was changed TO, how do you find out what it was changed FROM. Since he immigrated around 1891, the only way to find the papers is to know what the name was…
Is this all the information you have? I'd interview relatives - someone's likely to know his first name, what country he emigrated from or what port he came through. You may find someone who has a gem, such as a village of origin. You have an approximate year of immigration. If he came with his family and you know their names that should help you to discriminate among possibilities on ship manifests. If the 1891 date is correct, Becker may have come through Castle Garden in NY. Ellis Island opened in January, 1892. See http://www.castlegarden.org/searcher.php
Once you've got it narrowed down with further information you have a better chance of searching or browsing the archives. ISTG has a lot of good stuff, but not well organized. There are several Ellis Island sites. If you have a village in Europe, the late 19th Century genealogy is often well researched.
If you need to guess at the European surname, find a site that lists 19th Century surnames for the country of origin. Here's one for Belgium - http://www.vrijwilligersrab.be/PR-H-Letter.asp
There Becker is very common, but there are dozens of variants,, such as Backer and Bakker.