When does Gandalf realise that Bilbo's ring is the One Ring?

Gandalf did not know then that it was the One Ring. He simply suspected it. He realised Smeagol had called it that in the past and understood then there was an even deeper magical power behind this than he realised. He suspected it could be the One Ring, but he needed proof and to know for sure.

If you remember, he left the Shire immediately to learn more information. Whilst in the movies this departure is a fairly short one, in the books Gandalf is gone for 17 years, searching for answers.

You may remember in the movies he finds an account of Isildur, buried deep within a library (at Minas Tirith, in Gondor). It states as this script shows:

It has come to me...the ring of power! It shall be an heirloom of my Kingdom...all those who follow in my bloodline shall be bound to its fate, for I will risk no hurt to the ring...it is precious to me, though I buy it with great pain...

The marking upon the band begin to fade...the writing which at first was as clear as red flame, has all but disappeared...a secret now that only fire can tell...

Gandalf rushes back to Frodo and has him cast the ring in the fire, as a final test. At first it seems the situation may not be as feared, as the ring remains plain. As Frodo starts to notice the Elvish lettering though, Gandalf's fears are confirmed:

Frodo: It's some form of Elvish...I can't read it.

Gandalf: There are few who can...the language is that of Mordor, which I will not utter here.

Frodo: Mordor?

Gandalf: In the common tongue it says, "One ring to rule them all, One ring to find them, One ring to bring them all, and in the darkness bind them."

It was at that moment that Gandalf knew.

It's also worth pointing out that Gandalf's suspicions were low before this event, as Saruman had led him and all the wizards to believe the ring had been lost (from Tolkien Gateway):

In T.A. 2953, the Wise gathered once more to debate about the Rings of Power. Saruman quieted the Council claiming to have the knowledge that the One Ring was lost forever in the Belegaer.

As Saruman was at the time a wise and trusted leader, none of the wizards like Gandalf had reason to doubt him. To give some context to the time, Bilbo's birthday at the start of the Fellowship of the Ring was in 3001 (48 years later).

Furthermore, to delve into the lore of the books a little more, Gandalf started searching for Gollum when he left the Shire in 3001 (with the help of Aragorn). He returned to visit Frodo in 4 year intervals until 3008. He didn't return again until 3018.

Some time between 3009 and 3017 Gollum is captured by Sauron and tortured. He is eventually released in 3017 and is captured by Aragorn in the Dead Marshes. In the same year, Gandalf reads Isildur's scroll.

Finally, in 3018, Gandalf returns to Frodo and the events unfold as you know.

First of all let me say one thing: Tolkien's son, Christopher (who, for the records, published some of the unfinished books of his father), tells that JRR used to read him all of the stories (from LOTR, The Hobbit, Silmarillion, Unfinished Tales etc.) from simple sketches when was about time to sleep. He's also sure that those sketches were JRR's work cause he saw him write every line of them. So it's not like The Hobbit wasn't meant to be a prequel. JRR simply wrote The Hobbit and then wrote something to continue The Hobbit's story. So yeah, it was meant to be a prequel.

Btw JRR's universe is incredibly large. One that even Star Wars and Star Trek put together can be compared with... So to have something clear you have to read EVERY-SINGLE-AND-WHEN-I-SAY-EVERY-SINGLE-I-REALLY-MEAN-IT book and tale he ever wrote. Even the ones published by Christopher.

Since I'm really gentle I feel like sharing these info with you xD So here we go: start from the premise that Gandalf is one of the Maiar, the ones that assisted to the foundation of the world. Something turns on in my mind now: what does he know about what was, is and will be while "trapped" in a human body? Because, of course, if he knows everything then it's safe to assume that he did know about the ring since the creation of the world. But then we have to accept that, as a human being, Gandalf's powers are curtailed. So yeah, he could know where the future is going and have premonitions sometimes but he certainly didn't know that, for example, Sauron would be destroyed. The doubt is still there... So let's search the solution somewhere else... Unfinished Tales, maybe...

"In that far distant time I said to a small and frightened Hobbit: Bilbo was meant to find the Ring, and not by its maker, and you therefore were meant to bear it. And I might have added: and I was meant to guide you both to those points"

Bilbo was meant to find the Ring, and not by its maker So, basically, Gandalf knew that Bilbo would have found, one day, the Ring. Now you can think whatever you'd like. I like to think that Gandalf knew everything, but the imagine of the whole story was blurred in his mind so he discovered every particular as it happened. So, talking about the ring, he knew that one was The Ring the first time he saw it in Bilbo's hands...