It really depends on the webservice. Some are pure REST but most are REST-RPC hybrids. Although the examples are mostly ruby and python, I would recommend RESTful Webservices.

So what would a REST call look like in perl? Well, if you install lwp-request, from the command line, it may look like:

$ GET -e http://foo.bar.com/something
[download]

Now you would inspect the http status code for success or failure (that's why you need the -e) and then parse the response - whether that's XML or JSON or plaintext or whatever.

If you're really lucky, there may all ready be a CPAN module for the service (Net::Amazon::S3). If you're going to write a REST client, LWP and XML::LibXML (or another XML parser) are going to be your friends. If you're going to write a pure rest service, CGI::Simple is the only module to support the http PUT method (I provided a patch to CGI but that hasn't made it's way to CPAN yet).