These things get easier if you check up the history of the area so you know what you are looking for.
Poland was in fact not under German rule in 1860 at all. This is because neither Poland nor Germany existed. Much of the areas that now consist of Poland was indeed under rule of political entities that spoke German, yes, but some were under the rule of other entities.
Gollub seems to be the town now called Golub-Dobrzyń. It was from 1772 a part of Prussia, which in 1871 became the main part of the German Empire.
So your great grandfather was most likely born in Prussia, but unless you can find out where we won't know for sure. He was married in Germany, though, and your grandmother was born in Germany. This means that most likely your great-grandfather served in the Imperial German Cavalry.
Of the regiments of the cavalry, the ones garrisoned closest to Gollub was the 5th Cuirassiers, garrisoned at Reisenburg, now Prabuty. So it's likely that he was a part of this regiment, although I don't know enough about the German Army and how it worked to rule out the others.
And now for the bad news: Much of the records of the Prussian and German armies burned up in WWII. So the likelyhood of you finding the records of great-granddad isn't that good. Since he was in the Army it's also not very likely that he was born anywhere near where he was stationed and married, so finding other records without knowing where he was born is like finding a non-magnetic needle in a haystack.
The army records are still your best shot. You can probably call the Bundesarchiv and ask for more information and help.