How can a non-miner store data in the block? If I am not a miner and would like to put arbitrary data in the block chain, is there currently any method or protocol to get a miner to add it for me?
There is a service named btcmsg which allows you to do this. Here is the announcement in bitcointalk. The website is at btcmsg.staticloud.com.

They use a simple protocol to write and read the messages in the blockchain:


  BTCmsg Protocol v1 (2011-09-18)
  
  Each message is represented by multiple payment which is calculated by
  the following algorithm:     
  
  
  Two first chars for message type ('01' for md5, '02' for ascii).     
  Then the message in hex (python binascii.hexlify).    
  Split the long string to groups of 4 hex digits.   
  Each group of 4 hex (e.g. 2 ascii letters from the message) is     represented by a payment in satoshi (maximum 0xffff=65535).   
  The service fee (composed of a fixed part and a variable part times     the amount of small payments required, minus the transaction fee) can be seen within the first transaction.