They say when an air filter is dirty, you should replace it.
However, I'm just not sure how "dirty" is dirty?
Is there some sort of easy test to determine whether I need to replace it?
I usually change mine as part of any service, so generally twice a year. Obviously this will depend on how much you use the car and what sort of environment you're in - if you drive it a lot in dusty conditions you may well need to do it more often.
As Gabriel says, its a cheap thing to replace, and a clogged filter will adversely affect your power and economy, so if in doubt, change it.
I used to change mine at the factory recommended change interval (severe service, since my car sees lots of dirt roads). I believe that was 15k miles. It was always pretty dirty looking when removed, but no differences in performance or MPG noted due to replacement.
Upsides to more frequent changes: - Cleaner air should mean more MPG and performance - Do it automatically with every oil change and you'll never have to give it any thought
Downsides: - Wallet is lighter (although, that weight reduction may also help performance ;-) ) - Chance of breaking fragile clips that hold the air filter box together (some cars) - Can be a royal pain to get to (especially on some newer cars)