There's two ways to verify users:
1) The users of your webservice will have to pass some authentication information along with their request.
2) The users will have to have a client X.509 certificate (either issued by you, or by a certificate authority like Verisign).
Method number 2 works because web service requests go through IIS, and IIS would authenticate their certificate.
SOAP uses method number 1 with their "envelope" part of the XML that gets passed.
Chip H.