As Au101 mentions, the first canon usage is in Harry Potter and the Deathly Hallows, where Peeves employs the sobriquet in an improvised bit of doggerel.
As for the first attested non-canon usage?
Well, clearly it was in 1999, to judge from this paper. It says very clearly, on page 8, vol D_y = 1: Voldy is the one. :)
But in all seriousness, the name is actually quite old. Here it is in 2002, from cosforums.com user LewsTherin:
Here's the factual part. We know that Voldy went to the Potters to kill
Harry and James. We also know that he did not need to kill Lily but
did so because she resisted him. She then sacrificed herself and
Voldemort's powers were broken when his AK curse failed. Run of the
mill stuff.
But here's a suggestion. We've always assumed that what happened was
that Lily's sacrifice created a counter charm that simply acted as a
shield and bounced the AK back at Voldemort, not involving Harry at
all. Here's where my theory starts going crazy. What if, this was in
fact, not the case? What if, it didn't bounce the curse back, but
rather absorbed it, using Harry's own power? Let me explain.
We know Harry is very powerful, and it is my opinion that he's the
most powerful wizard in terms of sheer magical power that has ever
lived. He outstrips Voldemort by a comfortable margin, and Dumbledore
as well. So, maybe Lily knew this. Maybe she knew that she, in her own
power, could not stop an AK curse no matter what the power of the
counter charm, but she knew about Harry's power, knew that it was even
greater than Voldemort's. She also probably knew that Voldy would come
for them, and thus started to prepare long before he came.
This page also has a 2002 date, although its timestamp says it was last modified in 2006. However, it does not reference events from Harry Potter and the Order of the Phoenix (2003) which would be quite relevant, so I think we can assume that 2002 is when it was written.
PREDICTION; The last of the line of Gryffindor will be the downfall
of the last of the Last heir of Slytherin"; So Voldy wants to protect
his own hide from Harry, so he tries to kill him.
Here is another page from March 2002, in Italian. It is about one of the age-old questions, Sauron vs. Voldemort:
Indubbiamente Voldy è più "cattivo" ..hehe diciamo che Sauron è un
"Chaos".. mentre Voldy è più un "Evil" :muhehe: :bapho:
"Undoubtedly Voldy is more 'bad'...hehe I say that Sauron is a 'Chaos'...while Voldy is more of an Evil'". (mwahaha Baphomet? maybe?)
And another reference here.
I can find no solid evidence from before 2001.
So the best evidence I can find indicates that the word "Voldy," used to refer to Voldemort, showed up on the Internet in 2002.
Why 2002? Well, it was during the long wait between Goblet of Fire and Order of the Phoenix. Voldemort had first appeared as an embodied character in Book 4. Maybe this had something to do with it. We shall probably never know.