When this system was first being discussed, Gavin was concerned that miner incentives were to ignore replacements because it meant extra work and the replacement might have equal or lower fees than before (or indeed, no fees). He proposed two solutions: one is to progressively raise the fee on each replacement. The other is to specify lock time in terms of blocks and then step it backwards once for each replacement, thus ensuring that by replacing the transaction you get to claim any attached fee earlier.
It should be apparent that both solutions can be implemented by whichever application is running the contract - the core Bitcoin network and software is agnostic either way.
Now, Gavin and I disagreed on whether this would actually be necessary. As I already pointed out, both solutions seriously reduce the utility of HFT because they limit how often you can update the contract. Instead of an online game billing you per second, maybe it can only do it per minute or per 10 minutes with the lock time solution because otherwise you run out of blocks, and with ever-increasing fees perhaps the contract becomes too expensive to justify after a while.
So it'd be nice if this ended up not being necessary. Experience indicates that rational miners typically don't pursue a short-termist profit-at-any-cost agenda - free transactions have always been included in blocks, miners include transactions even though you could avoid a lot of complexity by just not including any at all, etc. Some miners like BTC Guild have actually sacrificed significant amounts of money for the good of the system. You can see this in terms of rational self interest - miners earn Bitcoins thus it's in their interest for Bitcoins to be as useful as possible, as that is what gives them value. Or you can see it in terms of ideologically-driven altruism. Or both.
If I were to implement an application that used tx replacement, I would probably start with replacements that don't change the fees and don't count down the lock time field. We can then observe whether miners bother changing their software to behave differently, or whether the inherent utility of the application is enough to convince them to play by the default rules. Ideally at least one application made possible by this feature is a "killer app" - something so useful / unique / compelling that people want to obtain Bitcoin just to use it. If someone can find such an app, then rational miners should want tx replacement to work as reliably as possible because it boosts the value of their earnings.
There are some other misc details - reactivation requires that we bump the protocol version and start relaying non-final transactions to new nodes again. Those nodes should relay replacements but not let them enter wallets unless/until the wallet software itself can handle them better, for instance, by communicating via APIs anticipated confirmation times. This is something for individual wallet APIs to handle on their own, and just ignoring non-final transactions is a perfectly workable approach for Bitcoin-Qt.