It doesn't depend on how long you have a Ring for, it depends on how much you use it.
As Gandalf says to Frodo in Shadow of the Past:
A mortal, Frodo, who keeps one of the Great Rings, does not die, but he does not grow or obtain more life, he merely continues, until at last every minute is a weariness. And if he often uses the Ring to make himself invisible, he fades: he becomes in the end invisible permanently, and walks in the twilight under the eye of the dark power that rules the Rings. Yes, sooner or later – later, if he is strong or well-meaning to begin with, but neither strength nor good purpose will last – sooner or later the dark power will devour him.
Strong will or good intentions can delay the effect too.
Despite this we can make something of a guess and at least set an upper limit, based on the Tale of Years for the Second Age, published in Return of the King.
From this we see the following sequence of events:
- SA1500: The Elves begin making Rings of Power.
- SA1600: The One Ring was forged; presumably the other Rings had been completed by then.
- SA1697: Eregion is destroyed and Celebrimbor is killed. It would have been about here that Sauron captured the Seven and the Nine.
- SA1701: The Numenoreans drive Sauron out of Eriador.
- SA2251: The Ringwraiths first appear.
So this establishes a time-window of about 550 years between when Sauron would have been able to hand out the Nine Rings and the first appearance of the Ringwraiths, but this is an absolute upper limit (so far as the Nazgul - being the only actual examples of Ringwraiths that we have - are concerned). More likely that the Nine Rings were handed out at intervals over a longer period of time, and also likely that the Ringwraiths had formed for some time before they publicly appeared.
The other thing we know is that the second-in-command of the Nazgul, Khamul, was an Easterling; assuming a standard Human life-span and that he recieved his Ring at a median age, he would have had it for about 40 years before he became "undying".
But none of that should be read as indicating that the amount of time is in any way significant, because - remembering Gandalf's words (above) - the main determinant is how much you use it. So it's totally possible to have a Ring for a shorter amount of time - say, 10 or 20 years, but use it so much that you become a Ringwraith (i.e permanently invisible) in that time period.
I don't believe that there's any more evidence that can be brought to this.
Some general discussion around this.
Gandalf's comment above is very specifically in relation to the Rings of Power in general, and not to be seen as only relating to the One. Note that he mentions "one of the Great Rings", so he's speaking in plural, and note also that in the paragraph preceding the one I've quoted he equates "Great Rings" (same phrase, same capitalization) with the Rings of Power: "But the Great Rings, the Rings of Power, they were perilous".
There seems to be absolutely nothing in Tolkien to differentiate one of the Nine Rings from one of the Seven, aside from the species they were given to. We may therefore deduce that a Dwarf given one of the Nine would get gold-lust, whereas a Man given one of the Seven would become a Ringwraith. This is also supported by Gandalf's words ("A mortal who keeps one of the Great Rings" - note that he's not specific about which one of the Rings).
Gollum didn't have one of the regular Rings of Power, he had the One Ring (as did Bilbo and Frodo). It's possible that the One may have a different effect, although Gandalf's subsequent words seem to imply that it would have been much the same. I'll treat Gollum separately below.
So as for Gollum, again we have Gandalf's words confirming that he didn't use the Ring much:
For it was long since he had worn it much: in the black darkness it was seldom needed. Certainly he had never "faded".
Gollum was tough to begin with, but certainly not well-intentioned, and the 500-odd years that he had the Ring fit nicely into this time-window, but he didn't use the Ring much so he didn't become a wraith. Bilbo was both tough and well-intentioned, and mostly used the Ring for pranks (and escaping from the Sakville-Bagginses) but even so, after 60 years (when he was nearing the end of his natural life-span, which I believe is significant) he was starting to feel the effects:
Why, I feel all thin, sort of stretched, if you know what I mean: like butter that has been scraped over too much bread.
This is in keeping with the statement in Letter 131, where Tolkien says (in a footnote):
The view is taken (as clearly reappears later in the case of the Hobbits that have the Ring for a while) that each 'Kind' has a natural span, integral to its biological and spiritual nature. This cannot really be increased qualitatively or quantitatively; so that prolongation in time is like stretching a wire out ever tauter...
Taken all together the evidence as I see it leads to us concluding that:
- The amount of time you have a Ring of Power for isn't really important.
- How much you use the Ring is the primary determining factor in how long it takes to become a Ringwraith.
- Being strong-willed and/or well-meaning can delay the effect.
- The effect depends on what species you are rather than the Ring you are given.