As pointed out above the 1MB limit is arbitrary and can be raised in the future.
What must be done to raise the limit?
A hard fork will be necessary and one will want to proceed in a cautious manner to protect the integrity of the network and ensure users are not exposed to any unnecessary risk.
Here is an example of how the process could occur (version # for both clients and blocks in this example are arbitrary and just used for illustration purposes):
1) Test this process from start to finish on testnet.
2) In a future version of Bitcoin client (1.0.1) add support for new block version (version 2). By default mining nodes will still create version 1 blocks at this time. In 1.0.1, ver2 blocks >1MB height they are flagged as non-standard and will warn issue a warning to the node, store the block and NOT exclude these >1MB blocks when making the best/longest chain selection.
3) Have users upgrade to 1.0.1. Monitor the usage of 1.0.1+ versions of clients and wait until a super majority has upgraded (no technical number but 80%+ has been used in the past).
4) Once super majority of nodes have upgraded set a cutoff date and use alert messages to warn older clients to upgrade or risk being forked off the main network.
5) After date in step #4 have miners begin to create version 2 blocks (but still soft limited to 1MB). A config flag can be used in 1.0.1 version of node to force the node into version 2 block mode (still soft limited to 1MB). This ensures all nodes have the ability to run the same codebase but still preserve their ability to support or not support the new block version.
6) Decide on a block height to implement >1MB blocks. This should be 10,000 to 20,000 blocks beyond current block height. It would make sense for it to be a memorable number, for example if we were ready for the transistion today (block height 246,242) the change could occur at block height 260,000
7) Release a new version of the client (1.1.1) which above the block height decided in step #6, allows creation of ver 2 blocks >1MB and considers them standard (selected for longest/best chain). Version 1.1.1 would remove support for block version 1.
Use alert messages to warn nodes on versions older than 1.1.1 that they risk being forked off after the block height in step #6. As the block height approaches the messages should occur more frequently and with greater urgency.
9) The prior major version 1.0.1 can be coded with a failsafe node. Since it "understands" ver2 blocks and just considers >1MB non-standard it can use this to protect the user. The version 1.0.1 can be coded to look for double spends in the >1MB blocks. The node can also count the # of blocks received on chains marked non-standard (because they have 1 or more >1MB block) and if that exceeds 50% of the total blocks in the prior day the user has likely been forked off (because it is after the cutoff date). The node could then consider all transactions unconfirmed, prevent spending, and warn the user to immediately upgrade to avoid loss of funds. Users older than 1.0.1 would have on knowledge of version 2 blocks and are at greater risk however similar safe mode could be built into clients now which looks for >50% of blocks being future blocks versions.
End state (once the block height picked in #6 passes):
Miners can (but aren't forced) to produce blocks greater than 1MB.
All nodes on current version will see these larger blocks as valid and use them for selecting the best chain.
Nodes which are on obsolete versions have some protection against malicious attack (alert messages & fail safe mode).
No it isn't a particularly simple process and it will take some time but using a staged process like the above (just an example nitpickers) provide a transition plan and ensure both non mining and mining nodes are ready for the change.
