One possible avenue of research is to look for Naturalization records. You have the certificate and you know the court which issued it.
The National Archives' introductory section on finding Naturalization records is here: http://www.archives.gov/research/naturalization/#find
For records prior to 1906, they say: "Contact the State Archives for the state where the naturalization occurred to request a search of state, county, and local courts records."
The Illinois State Archives has regional depositories for local records which have been turned over to the state archives:
Illinois Regional Archives Depository (IRAD) System
The State Archives administers a system of Illinois Regional Archives
Depositories (IRAD) to manage the archival records of local
governments. Local governments which have transferred records to the
regional depositories include counties, townships, municipalities and
school districts. Located on seven state university campuses, regional
depositories house and service those records of local governments
which have been appraised as having long-term values and have been
transferred to the Archives. Records include: naturalization records,
including declarations of intent
If you can find the "second papers" or Petition for naturalization, those papers might have the information about his arrival in the US, which would narrow down the search for any passenger lists that might be available. (In my own research, we have notes that came down through the family about the arrivals -- the arrival dates were not accurate, but the ship names were correct.)
The best process for searching the manifests will depend on the arrival date, but I recommend the One-Step Webpages by Stephen P. Morse at http://stevemorse.org/ .
Since this answer was first written, a court record about his Naturalization has been found -- see Naturalized in 1896, but cannot be found anywhere in the US 1900 or 1910 censuses?. It did not list his arrival, but there is other information that could be clues to further research.