Split the private key using Samir's Secret Sharing algorithm and give several trusted parties a fragment. For example, a 3-of-5 scheme where you give a fragment to a spouse, friend, family member, lawyer and bank deposit box. Any 3 fragments can be used to recover the private key. A short instruction on what Bitcoin is and how to use the private key you can spread more liberally to your beneficiaries.
Even better, use multisig transactions. That way your semi-trusted executors could prove to you (or others) that they still have the fragment you have given them without revealing the fragment (or getting the fragments together). If at some point one is lost, you can still get the others together and move to a new set of multisigs.
You also want to be clear to the executors about what you want to do with your coins. A notarized will is what you need here; feel free to stick it on a block chain to make it extra-notarized.