There are a small number of karaoke videos floating around on the net, but if you want to get a serious number of karaoke songs, you should try .kar files (midi files with lyrics sometimes also available with the extension .mid or .midi).

Personally, I use "VanBasco's Karaoke Player" which you can download for free at www.vanbasco.com which also offers a nifty search engine for aforementioned midi files with or without lyrics.