You don't say how or where you've already searched for an arrival record, but I'll assume you have made some searches and are unsuccessful. Sometimes a direct search for a record in the databases we have access to doesn't turn up anything. Now what?
You've made a good start by narrowing down a likely time of arrival. To find records, let's make a research plan. We have a question on the site Tracing US ancestor back to Germany? which talks about finding records for an immigrant who came over at a different time period. Rather than repeat a lot of that answer here, I'm going to follow the outline and address what records might be available for your great-grandfather's time and place.
If you haven't done so already, make a timeline of Henry and Hulda's lives, along with a list of material (from family papers and from your research) you already have about them. Review that material, working backwards in time. We start with the death and probate records, if we can find them, because they give the most complete picture of a person's life, and they set the date bounds for other searches.
In this case, their dates of death would tell me whether or not I could get any clues to their date of arrival from census records. The US National Archives and Records Administration (NARA)'s guide Clues in Census Records, 1850-1940, lists which census years have information about immigration and naturalization:
- The 1900 census (column 16), 1910 census (column 15), 1920 census (column 13), and 1930 census (column 22) each indicate the person's
year of immigration to the United States. This information should help
in locating a ship passenger arrival list.
The 1900 census (column 18), the 1910 census (column 16), and 1920 census (column 14), and 1930 census (column 23) indicate the
person's naturalization status. The answers are "Al" for alien, "Pa"
for "first papers," and "Na" for naturalized.
The 1920 census (column 15) indicates the year in which the person was naturalized.
These clues may lead to naturalization records.
If you can find these early 20th-century census records, you may find information about the date of marriage, too:
The 1900 census (column 10) and 1910 census (column 9) indicate the
number of years of marriage for each married person.
We look for Naturalization Records because for some periods, the records give the date of arrival and the ship the immigrant arrived on. This information may not be accurate but often it can help us narrow down the time period well enough that we can find the records (i.e. the ship name may be correct but the date of arrival may not be).
A good place to start when looking for records is the FamilySearch Research Wiki. Their article on Virginia Genealogy directs the user to a collection of Virginia, Naturalization Petitions, 1906-1929. These are District Court (Federal) records digitized from Microfilm held by NARA.
A place search for Richmond Virginia (independent city) shows the Family History Library also has Naturalization petitions and declarations, 1867-1912 which is a digital collection of US Circuit Court records.
Before 1906, naturalizations could be performed in the local courts, so there may also be records in courts in the area your great-grandparents lived. They may not be in collections which are specifically titled as naturalization records, which can make the search challenging.
Other things to consider -- people rarely immigrated to the United States alone. They often had assistance from other family members or friends. If your great-grandfather was connected with an industry, he may have been recruited. For my husband's family, many people came to their town from the same town in Germany because the companies wanted the skilled workers from that area. You didn't mention if your great-grandparents had any siblings -- you might be able to find information in the records of relatives or associates that could lead you back to your great-grandparents' arrival records.
If you can't find anything with a direct search, broaden your search to include family members and known associates. Newspaper research can reveal what churches and organizations people belonged to -- city directories often have information about the churches and organizations in the back of the directory. Keep track of where you searched and how you searched, and note any spelling variations (and indexing monstrosities) that you find. Search all the sites that have a particular record set in case the index at one site is faulty, and be aware that in some databases, there may be entries which have no name associated with them at all. Be creative and think of other ways to search that don't involve searching by name.
Research Guides and other resources: