I've just updated an iPhone 4 and an iPad 2 to iOS 5, and turned on iCloud, with syncing of Bookmarks enabled on both. And they are tied to the same Apple ID too.
For both devices, iTunes says "Your bookmarks are being synced with your iPhone over the air from iCloud. Over-the-air settings can be changed on your [device]"
So I expected that if I deleted a Safari bookmark on the iPhone, the change would get reflected in the Safari bookmarks on the iPad.
This update hasn't yet happened, after around 5 minutes.
(But photos do get updated almost instantaneously, I see)
Do I need to do anything special to force bookmark changes to be rolled out to the other device?