You guys must really beat on your cars, almost at 20K and mine are still fine.
I would say change them every 30K for a daily driver. If your car is at track day a couple times a month, or if you hit lift a lot, change them every 15K.
Think of it like oil changes, the more you push the limits of the car, the more often you change the oil... same thing.
You can buy these at the parts counter, or off the internet from one of the many vendors that sell toyota parts. You can try a conventional auto-parts store (like Car Quest, or one of the places that the shops get their parts from) but they may not have it in stock. Autozone and crap boys won't have it, so don't even try them.
You want rocker shaft set bolts (if you ask for "lift bolts", they will look at you funny and not know what you're talking about)
Toyota Part# 90105-06293 (Bolt, Flange) in catalog)
I have posted the TSB at my webserver... download it soon, because I will be relocating it to a new server in about a month or so.
You can find it at the following link:http://homepage.interaccess.com/~wcsi/Lift_Bolt_TSB.pdf