When I have questions for which no direct answer seems to exist, my answer to the question Are there any other records here in the US which might lend a clue? is anything you can lay hands on. It may be that the problem can only be solved with indirect evidence, in which case, the more bits and pieces you have, the better.
For the case which was most comparable to yours, I had to study the entire sibling set to discover the names of the adults in the family group who immigrated. This led to the discovery of a previously-unknown marriage, and contact with a descendant of that first family, who had already gotten some of the records from across the pond. If you haven't already made a timeline for the entire family, and plotted the family's history as a group, start there.
This is the time to widen your search and look at friends, associates, and neighbors -- to look at the history of the churches they attended -- to see if there are any social histories about the immigrant communities in all of the towns in which they lived -- use every bit of information you can find to answer this question.
It may be difficult because Joseph's occupation in the 1880 Census is Labourer -- when the occupations are more specific, it is easier to use the history of the industry to discover migration patterns. But if you work backwards systematically through the family's timeline in the USA and draw on social history to give you context, you may be able to fill in some of the gaps. Contemporary travel guides that were marketed to new arrivals may show the routes people took.
Also consider the reasons why you might not have found immigration or naturalization records. Is there any chance the family might have come through Canada (before the border crossing records, and before passenger lists)? When did other members of the community naturalize, and what events may have played a role in their decision to seek naturalization at that time?
Fleshing out the history of their communities in the USA may yield clues that will make it easier to establish that you have the right family, once you are ready to hire someone to research for you in Poland.
These webinars illustrated some of the research techniques (both using German immigrant communities as examples):
- F. Warren Bittner, CG, on Complex Evidence, presented on 24 February 2015 by the Board for Certification of Genealogists, and available for viewing (for a fee) at Vimeo; also scheduled to be repeated in the Legacy Family Tree Webinar series on 28 October 2015)
- Michael D. Lacopo, "Incorporating Social History into your Genealogical Research", presented on Wednesday, April 15, 2015 by the Southern California Genealogical Society (recording and handout available to members) webinar schedule
- Thomas Jay Kemp's webinar GenealogyBank - The Power of Finding Our Ancestor's Stories and postings about passenger lists on the Genealogy Bank blog demonstrate how ethnic newspapers published news about ship arrivals and news items about people in the community and in the 'old country' -- his examples are from Irish-American newspapers, but if you can find Polish community newspapers, you may find similar items. WorldCat is a good resource to find historical newspaper holdings and reference works about them, such as American newspapers, 1821-1936 : a union list of files available in the United States and Canada. For tips on searching for ships by name, see their blog post My Ancestor’s Trip to America: Newspapers Tell the Story.
Search for webinars and articles from other researchers who also have families in this area, especially if they came from Poland, and look at their case studies to get clues for more resources. I've found wonderful resources I never would have thought to look for by reading blogs written by people who are also doing research about the communities in which my families lived.
Via JSTOR.org, I found a doctoral dissertation about the German immigrant community I was studying. Via Google Scholar, I found someone's masters thesis about the changes in retail, which shed light on the business owners I had in my tree. One especially useful tip from Michael Lacopo: when you find local histories, read the bibliography to see what works the author cited. On Google Books, I've found period travel guides that list suggested routes of travel. You never know what scrap of information will give you the Eureka moment. Look everywhere, and at everything.
When searching for Naturalization records, it is important to look at the timeline and be aware of the changes in the laws regarding naturalization, especially for women. See NARA's Prologue magazine for these articles by Marian L. Smith:
This two-part article is especially helpful for discussing why we don't find as many records for women. It discusses the cases where women were likely to apply for naturalization on their own, and when women's naturalization was derived from their husband's.
Another rich source of information that will not be available to all families are US Passport applications. See NARA's Know Your Records program video Passport Applications, 1795-1925 on their YouTube channel for an introduction to the records in this record group. If your family has members who traveled often, you can get all sorts of interesting information from these records. The video is especially helpful because it discusses accessing the records via the index, so the researcher isn't completely reliant on an online vendor's computer index to find the records they need.
Finding immigration records can also be hit or miss depending on the date and place of the immigrant's arrival. The introduction to NARA's page Immigration Reference Reports gives this abbreviated timeline:
Immigration records document the arrival of aliens and return of U.S.
citizens to the United States from foreign ports from 1820 to the
early 1980s. Before then, individual ports compiled their own records,
which are not available at the National Archives. The U.S. Customs
Service maintained inbound passenger and crew lists from 1820 to 1890.
In 1891, the Immigration and Naturalization Service (INS) controlled
entry into the United States. Starting in 1895, immigration officials
tracked border crossings from Canada as well, and from Mexico around
1903.
Marian L. Smith, in her webinar presented on March 27, 2015, "How Castle Garden Records burned in the Ellis Island Fire", talked about how the passenger lists that had been kept by the New York State Commissioners of Emigration between 1848 and 1890 were transferred to Ellis Island, just before the fire of 1897. So for a New York arrival, we only have the US Customs lists for the 1860s, not the more detailed passenger lists that would make it easier to match up arrivals with our families if the names are mis-indexed.
For an overview of what passenger lists we do have, Joe Beine's German Roots website has many good guides, including Finding Passenger Lists & Immigration Records 1820-1940s: Arrivals at US ports from Europe, Ship Passenger Lists and Records Online, and Finding U.S. Naturalization Records.
Reviewing the individual record groups and then reviewing your own findings from other records can also turn up clues. NARA's Know Your Records playlist on YouTube has videos on immigration and naturalization records held at the National Archives that also give some insight into records held at the state and local level. (This series is ongoing so more videos may be added later.)
See also Prologue Magazine, A Gold Mine of Naturalization Records in New England by Walter V. Hickey for an overview of the WPA project that created the New England naturalization index. New York records were also microfilmed and are on NARA microfilm publication M1674 (294 rolls).