Look at Peter Todd replace-by-fee effort. There's a lengthy recent discussion on bitcoin dev mailing list and also here on btctalk you shuold be able to find some threads abou it.
Lengthy indeed. I'm reading up on this now - it's seems like a cool feature. I guess it will take time to get into GUI wallets but it's probably common to accidently make a stupid send and be willing to resend with a higher fee.