[full version of article A Web Services Taxonomy (PDF 84k)]
A Web Service, according to a standard definition, is "a software system designed to support interoperable machine-to-machine interaction over a network." 1
To put it another way, a Web Service is some useful service offered (usually) on the Internet, designed as a sort of building block you can use any way you want.
So, for example, Google Maps, a free service that dynamically draws maps of any location and locates addresses, has been used by thousands of people to build new services such as crime-report maps and real-estate listing tools,
Another way to wrap your mind around Web Services is to consider a range of well-known ones and what they do. That's what the chart below does, with services such as Paypal, Google, Twitter, and Sabre, the airline-reservations system. (click on chart to see full-size):