How can I prove that I destroyed some bit coins? If I wanted to destroy bitcoins, and prove that it was done (with relative certainty), what would I need to do?
If you just want to make it clear that you no longer own them you can just send yourself 1 santoshi and put the rest up as a fee. If you want to destroy them there are a couple decent address to send them to in What is the Bitcoin equivalent of /dev/null?

EDIT: there are better answers here: How to generate a valid bitcoin address for destroying bitcoins?