If you were to take the sum of all things assigned the attribute of "cloud computing" you would have a definition that encompasses every technology know to man that ever though of being on the web. I think understanding what the cloud is can start with understanding what it is not.
First of all a remote connection to a terminal session to run applications on a desktop located somewhere far away is not cloud computing. It is a pretty cool thing to be able to do, and the technology behind it is pretty cool as well, but it is an "old school" solution to the very problem that the cloud addresses, which is what if I need access to my information and I'm not near my computer or in my office. When I say "old school" - you must remember that this type of terminal processing is where we started with mainframe computers and dummy terminals. Use this technology where it is beneficial, but don't call it cloud computing.
Secondly cloud computing is not just a really fancy web site. If your web site allows customers to log in, place orders and check order status - you have accomplished a very important business process using web technology, but you are not cloud computing. Again this type of technology is really cool, but not really cloud.
So what then is cloud computing? ... Well that is an excellent question. I believe that at the core of cloud computing you have processes, data and communication elements that are not directly tied to a specific application (web or otherwise). These elements are available however to any number of applications that my require them, or may even be used in a custom solution. There is also an element in the cloud of combining these various elements from various sources on the web, so for example you may have a web portal that uses Windows Live to authenticate a user, mapquest to provide mapping data, and weather information from weather.com. Additionally this portal may also include elements from your own network to pull together a complete experience. And just to really drive the point home this same experience may be available in another applcation that uses web service to gather the necessary information, or even on your phone.
In the cloud the various experiences are centered around processes that you are involved in, rather than a particular place you work - or even a particular computer or piece of software. Microsoft has made Exchange (amoung other things) available as a service in the cloud. Now you can setup Exchange without having to worry about the server. Once setup it addresses the processes around contacts, calendaring and messaging. Any number of applications including a web portal interface, outlook, your phone or some custom application can help you perform the processes your require all centered around a single source of data.