How do you tell when it's time to replace a cassette?
Are there any specific wear patterns on the teeth to watch for or symptoms specific to a worn-out cassette?
Without experience, or obvious damage, a cassette gauge like the one from Rohloff, or mileage are your best options for deciding when to replace a cassette. For me, a good rule of thumb has been:
That is, I change my chain every 1200-1500km. I change the cassette on the 5th time I change the chain. And I change the chain ring set every other time I change the cassette.
This is an example of an obviously worn chainring.
This is an example of a worn cassette.
EDIT: this answer uses an extreme example, perhaps irresponsible, I admit, but which tried to state some things which I think are valid considerations regarding the question asked:
I hadn't, and would not recommend, to measure the wear on the cassette, but on the chain.
If you put a new chain with a cassette, and it doesn't skip, the cassette is ok, even if the teeth are a bit thinner than new. That is possible if you change the chain often, always for a new one: then the cassette wears out slowly, but the teeth are never deformed like a ramp (shark teeth). I elaborated a lot on this in another answer: http://bicycles.stackexchange.com/a/7880/2355
Of course, when the teeth are SO THIN that they are pointy, or its width is significantly reduced, perhaps it's time to convert the cassette into a set of ninja shuriken (just kidding).
There could be problems with the indexing of gears if you are a fan of ultra-precise shifting, but that usually is not a great problem, and as far as I know don't cause damage to other parts of the shifting system, at least if it is not necessary to force the lever to shift up (could stress the pulleys - usually this is not the case).
At last, the proper way to measure for the CHAIN wear is the distance between pins, that should be exactely half an inch for each consecutive pair of pins. This can be measured in two ways:
Just for the record, this is a current picture of my internal-gear-hub bike with surely more than 25 thousand kilometers with the original cog. I must have used some eight chains on it, always replacing via measuring, either with a gauge or with a ruler. It works without issues (no skipping, no falling off, no grinding sensation). This is too much, I recommend not going so far. I has paid itself a long long time ago.
I agree with the comments that say that chain wear governs. But be sure to test after changing the chain for skipping. Put the chain on the cogs you use the most and pedal vigorously. It will be obvious if the casette needs replacing.
The wear pattern I have usually noticed is that the teeth become more "pointy" or "hook" shaped. Also, Rohloff makes a tool called the HG-Check tool for Shimano cogs. Not sure if it works for other brands.
The main symptoms I've noticed are rear chain skipping and poor rear shifting. However, these symptoms have multiple causes, so you want to rule those out before spending the money on a new cassette. (For example those symptoms can indicate chain, cable, and derailleur issues.) And at times, one may only need to replace a cog or two, rather than the whole cassette.
A major key to cassette lifespan is keeping the chain clean and lubed.