The nine men that took the Rings of Power from Sauron, turned into Ringwraiths eventually.
How long do you have to have a Ring of Power in order to turn into a wraith?
Sméagol had it for many years and didn't turn into one. Is there a difference in the period of time required to turn between species?
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:
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 16 Rings of Power were forged midway through the Second Age (somewhere around SA 1500) and were intended from their very origin to seduce and thrall the mortal rulers of Middle-earth to evil. Unlike the One Ruling ring, their magic was deliberately intended to ensnare mortals. The Nine Rings that Sauron used to corrupt Men to his service caused them to became the Nazgûl, his bound servants.
The Nazgûl first appeared at approximately 2251 of the Second Age. That would mean on the very outside it took 751 years for the Kings of Men to become Nazgûl. It's likely that it didn't take that long depending upon when each king received his ring and when he actually turned. He could have turned much sooner but laid low until 'called forth'.
