The encryption key must reside only on trusted (client side) devices to allow your data to be hosted by a third party without them actually seeing your data.

(Golf clap)... and in practice how would one verify such a scheme?

What do you mean?

Verifying that data going across the wire is encrypted is fairly easy to do.

You check the data going out is encrypted and that it is encrypted when it comes back. Is that enough verification for you?

Depending on how much you trust the vendor you can go further - run it in a debugger and check where it gets the key for example.

How do you verify that the key is not being sent over the network by malicious software?

How do you check if any malicious software is doing something? You check what files are being read, and you correlate with network traffic.

You lock down access to files like private keys as much as possible to minimize the possibility of this.

Tiny device on your keyring?

For example (not affiliated): https://yubico.com/

There's an interesting area of research called Homomorphic encryption (http://en.wikipedia.org/wiki/Homomorphic_encryption). In this schema, certain properties of the data are maintained even after encryption. In the general case you would be able to stored encrypted data in the cloud and perform operations on it without needing to decrypt the data.

Client side encryption and open source client software a la Tarsnap.

Client side encryption doesn't seem to fit with the ChromeOS concept. All your information is in your Google account, all your documents on Google Docs and none of it is encrypted as far as I know (Open to Correction). An engineer at Google could theoretically look at all your bookmarks, documents, browsing history etc. Add aggressive US "anti-terror" laws into the mix and it looks like ChromeOS is not a good choice for those looking for real privacy.

If the government wants to read your documents, it's just as easy for them to get a warrant to search your house as it is for them to get a warrant to compel Google to give them your docs.

Except, as we've seen with wiretapping and so many other data breaches, if it's 'just there' and can easily be indexed and searched with the click of a mouse, then it will be. Searching someones house requires proper channels to be followed. Looking at files on a PC is so much easier, can be done without the person knowing and is, imho, too great a temptation to resist. The emergence of laws in the US to make such access as easy and automated as possible proves this.