What will be required to increase the "soft" 500KB per-block data limit We've alerady hit the point where a block has become 90% full, thanks to the popularity of SatoshiDICE.

The limit can be increased from the 500 KB max per-block in the software to 1 MB per-block limit in the Bitcoin protocol, reportedly.

To increase this to the level allowed by the protocol, is it just a client update for miners, or does it require a new client for everyone who needs to be able to accept blocks with the larger limit?
The 500kB limit is related to the fee rules. Miners won't include transactions into their blocks unless they have at least some minimum fee. The Satoshi client determines the minimum fee (for miners -- relayers and senders use slightly different rules) like this:


When the block currently being mined is less than 27kB, certain transactions are allowed without any fee.
When the block currently being mined is less than 250kB, the fee is 0.0005 BTC per kB of transaction size.
After 250kB, the fee per kB increases as the block size increases to an asymptote at 500kB. At 500kB and beyond the fee is infinite and no more transactions will be accepted.


To increase the limit, we'd only need a few significantly-sized miners to change their fee policies. DeepBit already doesn't use the Satoshi client's dynamic fee increase after 250kB, though I think they still have a limit at 500kB.