First a few definitions. Cloud storage is storage that is accessible via the Internet usually from a device like a laptop but it could even be from an iPhone. As with most "cloud" related technologies, the location of the storage is not usually an issue.
Cloud computing is essentially a more advanced form of web hosting although the computation can be more than just delivering web pages to clients. The Amazon Elastic Compute Cloud (Amazon EC2) and Eucalyptus are examples of cloud computing infrastructures that are actually compatible. The Eucalyptus Public Cloud (EPC) is an open source version of Eucalyptus.
Essentially these platforms split the computation side from the storage side providing elastic compute (EC2), elastic block storage (EBS) and storage (S3) linking them all via the network. The key to the network support is that it is essentially a virtual private network (VPN) that can be linked to the Internet or other networks. The components are usually managed as a group and can be scaled as necessary with commercial ventures charging based on various usage metrics.
But back to cloud storage. Cloud storage differs from EBS and S3 in that the storage is normally access from a device like a PC or smartphone but, in this case, the storage is viewed as logical shares as if they were on a network file server. The client devices need a mechanism to access the data and manage the storage but it is at a higher level than something like EBS.
Internet-based backup services have been common for a number of years and they fall into this cloud storage category. Normally the backup is made from a PC and stored on an Internet-based file server. Various applications are used to provide the backup and restore facilities. Some are browser-based.
The up and coming cloud storage is often called Plug Computing, a term coined by Marvell Technology. Some Marvell's Armada line of microcontrollers and microprocessors target this environment and its SheevaPlug was the basis for a number of Plug Computing platforms.