Many people and companies have debated the exact definition of Web services. At a minimum, however, a Web service is any piece of software that makes itself available over the Internet and uses a standardized XML messaging system.
XML is used to encode all communications to a Web service. For example, a client invokes a Web service by sending an XML message, then waits for a corresponding XML response. Because all communication is in XML, Web services are not tied to any one operating system or programming language--
Java can talk with Perl; Windows applications can talk with Unix applications.
Beyond this basic definition, a Web service may also have two additional (and desirable) properties:
First, a Web service can have a public interface, defined in a common XML grammar. The interface describes all the methods available to clients and specifies the signature for each method. Currently, interface definition is accomplished via the Web Service Description Language (WSDL).
Second, if you create a Web service, there should be some relatively simple mechanism for you to publish this fact. Likewise, there should be some simple mechanism for interested parties to locate the service and locate its public interface. The most prominent directory of Web services is currently available via UDDI, or Universal Description, Discovery, and Integration.
Web services currently run a wide gamut from news syndication and stock-market data to weather reports and package-tracking systems. For a quick look at the range of Web services currently available, check out the XMethods directory of Web services.