You have to remember that Prussia was the largest state in the German Empire - stretching from well west of the Rhine to the Russian border (now Lithuania). I would suggest you google up some maps of Europe in the 19th century and you will begin to get the picture. If you could find even a tiny clue as to the name of a place - town, city, village - it would be a great help but until you do this I fear your searching will be looking for a needle in a haystack. I assume they applied for naturalisation - that might give a clue to a more specific place. The daughter's birth certificate/ baptism certificate, marriage record or their death certificates might also be somewhere to start looking. Looking for an obituary in a local paper might also be useful. Good luck.