Cloud Computing emerged from the idea of outsourcing computer hardware since the 1960s, with John McCarthy who theorized of an eventual computing outsource model. But more than outsourcing, it is about sharing resources. One could argue that mainframes - one of the first large scale computer systems that were shared by many people within large enterprises due to their high costs - were the first Clouds. But as @tracylezama notes, the notion of "on demand" was missing. On the other hand, Application Service Providers (ASPs) provided on-demand services since the 1990. However, they moved the complexity of computing from the enterprise basement datacenter into the ASPs basement datacenter; the machines were still the same, no real resource sharing. With the technology of "virtualization" several virtual servers could run on one server. The current notion of Cloud involves a multi-tenant system - some kind of platform that allows secure and fair sharing of resources while a platform upgrade or feature added will be available for all tenants of the platform. The platform paradigm created the Cloud layers Software-as-a-Service, Platform-as-a-Service, and Infrastructure-as-a-Service.
For some time Cloud was marketed very coarsely as addressing two needs: reducing costs and reducing service provisioning times. Of course these are great benefits, and with no doubt important ones. But CTOs and CIOs have a more differentiated need than just "cheap and fast": increase the speed of innovation, increase precision of demand and capacity planning, reduce vendor and supplier dependencies, support business agility and new business, reduce interface complexity, increase service quality. As long as any technology or business model can address these common needs, CIOs and CTOs will jump on it. Cloud became a viable business model as soon as ecosystem players fine-tuned their message and catered to these needs - which became the benefits of cloud computing.
Cloud computing is a form of Internet-based computing, that functions in a way similar to an electricity grid and in which resources and information are provided on demand. One of the great benefits of cloud computing is that you don't have to make a huge investment in infrastructure. Instead, it is treated as a service and you only pay for what you use.
Good question! It has been hard to define what cloud computing is because the term has been severely bloated. (Infrastructure/Software/Data/Compute/Storage/Applications/etc..) As A Service are all cloud type offerings. But the one thing that it seems all "cloud" providers seem to have in common is that they are not "here"..
Certain implementation of cloud bears some similarity to "the grid" (at least for people trying to get funding for new projects in the academic and government labs).
Somewhat facetiously speaking, I think the term "Cloud" came from techies drawing on their white boards the logical layout of their network and components. At some point they are going to draw a line to a cloud which symbolized the Internet. Then when managers noticed that something had to added or moved they say something along the lines of "Why not just do it in that there cloud"! ... At which point the engineer gets sad.