Proof of burn simply means you have provably destroyed coins. The only way to destroy coins in a proven way is to send them to an address which is improbable to have been generated from a private key, and thus can not be spent.
Chancecoin is the first I've seen to use this way to generate their coins. The announcement for Chancecoin can be found here: https://bitcointalk.org/index.php?topic=528023.0
In here, they instruct people can burn bitcoins for a certain period by sending them to 1ChancecoinXXXXXXXXXXXXXXXXXZELUFD. The reason why we believe that this is a burn address and not a vanity address is that all but 6 characters seem to have been predetermined. The way you would find an address like this which you could send coins to is by running a loop.
- Start with 1ChancecoinXXXXXXXXXXXXXXXXXXXXXXX
- Ask bitcoin if that's a valid address
- If it's not valid, increment the last character by one and try again
After a billion or so tries (not too much in terms of 'mining') address 1ChancecoinXXXXXXXXXXXXXXXXXZELUFD is found which passes the validity check. For more info on address validity see: https://bitcointalk.org/index.php?topic=1026.0
This address is very unlikely to have been generated with a private key, or if so, it would show a big weakness in bitcoin and many other security practices. So we assume that the nobody has access to this private key.