iCloud is a service that was launched together with iOS 5. It is the successor to MobileMe. Allows for wireless backups of iDevices, and does a much better job at keeping contacts, calendars, and other things synced between devices. It also allows for purchases made on one device (such as an iPad) to show up on the users iTunes, iPhone, and iPod Touch, without performing any extra steps.
Free storage space is limited to only 5GB. While not everything counts (bought applications and songs for example) on a 64GB device full of photos and application data, this limit is reached quickly.
Also music cannot be stored in the cloud (but there are other services, like iTunes Match).
And for applications that you bought, but have been removed from the App Store (like VLC), these applications just disappear when you restore, so you still need a computer based backup.