The easiest way to get started with Web services is to learn XML-RPC. Check out the XML-RPC specification or read my book, Web Services Essentials. O'Reilly has also recently released a book on Programming Web Services with XML-RPC by Simon St.Laurent, Joe Johnston, and Edd Dumbill.
Once you have learned the basics of XML-RPC, move onto SOAP, WSDL, and UDDI. These topics are also covered in Web Services Essentials. For a comprehensive treatment of SOAP, check out O'Reilly's Programming Web Services with SOAP, by Doug Tidwell, James Snell, and Pavel Kulchenko.