Visible wear and tear, generally, unless the mileage is just so extraordinary given then circumstances, that you begin to fear for your safety (ie, don't use the same tire for 6,000 miles, even if it looks ok. better to spend 30 bucks on a new one)
Usually, it makes sense... somewhere in the broad window between 500 and 2,000 miles, it starts to look gnarly with cuts, cracking, or simply deep wear. How far you push it depends on your budget, and more importantly, your experience with that model of tire. Go with your gut...
...me, I tend to operate on a better safe than sorry formula.