So, when is a fee 'normally required' anyway? And, how old must a coin be before it's considered old enough to not warrant one?
The algorithm is a bit complicated. It's based on the size of the transaction (typically how many outputs and inputs it has) too. The default client has two thresholds, below one and it won't accept the transaction at all. Below the other and it will purge the transaction fairly quickly, but it will pass it on to other clients (who will likely do much the same). The basic rule is that a 'normally requires no fee' transaction must be under 10K (about 9 inputs/outputs total), have no output under 0.01 BTC,
Also, when the number of confirmations changes from 0 to 1 does that mean that a peer picked up the transaction and relayed it? Or that it actually found its way to a miner who accepted it and verified (i.e., confirmed) it?
1 confirmation means that it has been included into a mined block that has found its way into your client's block chain.