Sauron learned that Gollum had possessed the One Ring when Gollum was captured by the forces of the Dark Lord. We know that Gollum's obsession with the Ring eventually led him down a path to Mordor, home of the Ring's maker; as Gandalf says in book 1, chapter 2:
I am afraid there is no possible doubt: he had made his slow, sneaking way, step by step, mile by mile, south, down at last to the Land of Mordor.
We do not know in precise detail how Sauron learned the details of Gollum's history with the Ring, but it was probably not difficult. We do know that Sauron personally participated in whatever tortures were used on Gollum:
'Yes, He has only four on the Black Hand, but they are enough,’ said
(book 3, chapter 3). It is entirely possible that Sauron could simply recognize that the wretch before him had been twisted by the power of the Ring. In any case, Gollum does not seem have been terribly careful about what he said to whom, regarding his vengeful search for Bilbo Baggins and the stolen Precious. He might have told Sauron most of what the Dark Lord wanted to know quite freely, and even the information Gollum wanted to hold back, he would not have been able to keep secret. Gollum was a weak-willed creature, whose existence revolved entirely around his covetous lust for the Ring. He could probably not have endured even a ordinary regime of torture and kept his secrets to himself; there is no chance that he could have avoided revealing everything while under the cruel ministrations of the Ring's maker and master himself.