Can Craft easily be hosted across multiple servers? We are looking at Craft as our CMS but would love to be able to scale the installation across multiple Amazon EC2 instances.

Is this possible? 

Can all assets uploaded to Craft be pushed to S3? 

Is there any other data (eg sessions) that are stored on local storage that would likely cause a problem?
Entirely possible. There is some discussion of having Craft installed in a load-balanced environment here.

You'll want to have CRAFT_STORAGE_PATH point to a shared file system for all servers.

If you have sticky sessions enabled at a load-balancer level, then PHP sessions won't be a problem.  If not, then you'll want to set overridePhpSessionLocation to true and have the PHP session files saved on the same shared file system.