How can I provide data security over a Web Service

Are you just talking about using SSL?

As Encrypted said if you want the data being sent to your server to be secure you need to use SSL.  This stops people intercepting the data as it's being transmitted.

If you want to make sure only authenticated people can talk to your server using the service you need to add some authentication system.  If you want to severely limit access the usual approach is IP filtering where you only accept requests from specific other servers.

Doug

mainrotor if you are seriously looking for some security tips on your web service then you must follow the OWASP Web Services Security Project  and this Web Services this will help you a lot by following some set standards of security.