It makes things much simpler if you have a WS up and running that you control - Apache Axis is easily installed in a servlet container.
But you're right, you don't absolutely need one. http://www.xmethods.net/ lists many publicly available web services. What you need for a service is the WSDL and the endpoint, both of which are listed there.
Once you have the WSDL, you can create a Java client using the java2wsdl tool, which comes with Axis.