(Disclaimer: I work at Salesforce)
We at SFDC hear a lot about offers to businesses of "your own private cloud", which is essentially marketing jargon for something very un-cloud-like: running software locally, on your own servers, while you're completely responsible for the entire operation. It's a grossly disingenuous hijacking of the "cloud" terminology that I've found promotes confusion.
Most of the other responses here would match my own definition of the cloud: software, offered as a service, where all the underpinnings (data center management, software updates, redundancies, reliability) are abstracted away from you. The key is that you only need two things to access a cloud resource:
A web browser, preferably != IE6
An internet connection
When I explain the cloud to people who don't read HN, I usually make a comparison to Gmail and MS Office. You access Gmail through your web browser, and there's no local software to download. When Google releases a new feature or a bugfix or a security patch, there's no action required on your end. You're simply up to date the next time you connect.
Contrast that with MS Office, which comes on a CD/DVD, requires a local install process, and needs to be constantly patched for features and security. All of the work to maintain that software falls to you, the end user.