You intentionally write a double-spend. You write it with the same inputs and outputs, but this time with a fee. When your double-spend gets into a block, the first spend becomes invalid. The payee does not really notice, because at the moment the new transaction becomes valid, the old one becomes invalid, and the new transaction simply takes its place.
It's easier said than implemented. There would be a fair amount of work to make a client that correctly writes the double-spend, manages the two versions in the wallet until one is chosen, handles all the corner cases. Every assumption in the existing code is that you're not trying to write double-spends.
There would need to be some changes on the Bitcoin Miner side also, to make the possibility to accept a double-spend into the transaction pool, but only strictly if the inputs and outputs match and the transaction fee is higher. Currently, double-spends are never accepted into the transaction pool, so every node bears witness to which transaction it saw first by working to put it into a block.