i have only changed one set of stickers and that was on my 25th anniversary cube cuz those stickers really suck. but other than that, i havent changed any stickers.... i keep my fingernails pretty short, so they wont cut up the stickers.
so to answer your question- i would switch my stickers whenever they are falling off.
It varies depending on type of sticker and cube. For my main cube, I use textered tiles. They are probably close to a year old now and still look brand new.