If the service requires authentication (e.g. not anonymous) then you need to provide credentials for authentication. This can be in any of 3 forms:
1) Web forms, the cookie will be created when user logs in with their browser (typically only used in Ajax situations)
2) Basic Authentication (works well with WebClient, but you should use an SSL connection)
3) Digest Authentication (works well with WebClient, more secure than Basic Auth, SSL is more secure but this is better than plain text. Will not work with a typical XmlHttpRequest)
Additionally if the service was developed using Module Authorization then you configure the appropriate permissions for the user on the module instance, and send the module and tab id in the headers (I can't remember if querystring or cookies will still work too) of the request.
Finally if the service requires anti-forgery validation it is only intended for use in an AJAX situation. While I suppose it would be possible to hack up a solution that fetches the correct page and parses the forms and cookies in order to later post the correct values it is not trivial and not how the service was intended to be used.