My g-grandfather was supposed to have been in the Cavalry. He was born in 1860, where ?(Germany/Poland). I know at that time Poland was under German rule. Married in Gollub, Germany and my grandmother was born in 1890 Abbau, Gollub, Germany (now Poland). I have his marriage, and my grandmother's birth record.
How and where can I find his military record, if any?
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.
Military service was manditory in imperial Germany. Because riding was perceived to be easier than marching, there were additional horsemanship pre-requisites and longer service required for the cavalry, to equalize the demand. To some extent, a volunteer (rather than draftee) could apply to a regiment. My grandfather, a landowner's son from Silesia, served in the Leib-Garde Husars Regiment in Potsdam, in the early 1900's, which certainly had more cachet than the various cavalry regiments garrisoned closer to home.
Likely your ancestor came from a similar background. You might check for your surname in the addressbooks published before World War II to help narrow down the province or county (Kreis). http://adressbuecher.genealogy.net/ has a large collection digitized. So does http://search.ancestry.com/oldsearch/rectype/default.aspx?rt=37 . There were also Güter-Adreßbücher (property owner directories), published annually(?), that are available in German libraries; some are purchasable as used books or CDs.
If you have a photo of him in uniform, that might help an expert determine his regiment.
