Gartner's definition (I think) is that the computing takes place at a location unknown to the user, so almost every service is a 'cloud' service...for example your gas bill, or your TV services....both are run by systems many miles away and we (the end user) don't need to care how it operates.
In the hosting world, it can mean anything from pure marketing rubbish, to systems which are designed to be as highly-available and resilient/scalable as possible. So instead of having one server for one function, there are two, and so on.
But just like with 'normal' hosting there are an infinite number of variations from shared cloud systems to private-cloud / infrastructure-as-a-service systems (like AWS where you tell it how many resources you want and it gives them to you, and you're responsible for what runs on the system), to software-as-a-service systems (eg Kashflow - online accounting).
I appreciate this answer probably doesn't help at all so the best answer is to quiz anyone offering anything 'cloud' to find out what they're actually offering.