Assuming that Sharepoint web-parts are 'server' based (i.e. the request
to the web service comes from the Web Server running Sharepoint not the
client's browser) then you have a couple of options:

1. Use IIS - either restrict the IPs that can access your web service's
application or use Windows Authentication and only allow the user that
sharepoint runs under (assuming that isn't running under the end-user,
obviously).
2. Use WSE
http://msdn.microsoft.com/webservices/webservices/building/wse/default.aspx
(or your own Soap Headers) to require a username/password. You'll have
to include this in the requests from the web parts somehow.

Hope that helps - let me know if I'm way off target here.

Josh
http://www.thejoyofcode.com/