Currently the incentives for miners are the block-awards and transaction fees. Suppose I want to create a Bitcoin-like hash-chain for other purposes than storing coins (for example: storing messages), how could one create an incentive for miners to do the work?
Transaction fees, just like in the bitcoin blockchain.
The level of mining would then adjust up and down with the amount of usage. You might need to subsidize it to get any participation from the start.
If demand is too low where fees don't justify this, then demand is too low where fees don't justify this.
Perhaps you can use Namecoin, which already exists, to solve your problem? Namecoin can be used for namespaces other than just .bit domains.
The incentive for miners in most cases is the same - profit. Mining costs a lot of money, so miners would want to at least get their money back. On the other hand if you are supporting some worthy cause, you can get some people to contribute for free. An example of the latter would be SETI, or Folding@home.
So all in all, you would most likely have to pay the miners in some manner - either through Bitcoin rewards, or some new type of Coin, like Namecoin for example.