Hi
Well, your first reference point would be to obtain the marriage certificate that Tati has found for you; as she says, it should hopefully give you Frederick's father's name and occupation.
My reading of the 1881 Census is that he was born in Grumbach, Prussia, which is now part of Germany; and he was a naturalised British Subject.
So to check this out you would need to access the parish records for Grumbach and look for the birth of Frederick around 1840. Hopefully the birth record will show the same father's name as the marriage certificate.
You haven't given any indication on your personal details as to where you are in the world
but I'll assume you are living in the UK. To find your nearest LDS centre take a look at this:
http://www.londonfhc.org/content/other-uk-centresYou can order the film (I think it costs about £7 for two months) to your nearest LDS centre that has a film viewer, but as far as I know you have to go in person to the centre to make the order. It may take a couple of months to arrive as they will probably have to copy it in Salt Lake City and send it to the UK, but having ordered and viewed a number of European parish register films myself, it is well worth the wait!
The film number is 1528777 (from my previous link).
Regarding immigration, passenger lists between ports in Europe were not kept unless the ship was travelling further to The United States, Canada, etc, so you are unlikely to find your Frederick this way.
I can't see naturalisation records for Frederick at the National Archives, but many people became naturalised just by living here for a certain time (or just stated they were naturalised
):
http://www.nationalarchives.gov.uk/Kind regards
Gaie