First thing you will probably have to do would be to turn on Basic
Authentication in IIS on the SharePoint server. If the server is set to
use Windows Integrated then it is expecting the credentials in an
encrypted format that you won't be able to support from java. Then be
sure you are adding the UserID and password to the SOAP message. That
should take care of it. It's much easier to do this when making the
call from .NET. Then you just have to add the cached credentials of the
user to the credentials property of the webservice proxy.

I have to make this call from Java as I'm customizing a third-party
app to include content searches from SharePoint. For those folks
that are searching from and using SharePoint, we need Windows
Integrated authentication  - can we have both? Or am I looking at
extending the webapp to use the alternate authentication? Also, I
really don't want to pass the password - are there any other options?

You don't need to use an alternate authentication. You just need to
enable Basic authentication  in IIS. Windows Authentication can be set
to work as either Windows Integrated, Basic, or Advanced Digest. They
are all the equivalent. It's just that Windows Integrated requires
specific browser support to encrypt the userID and password. You won't
have that support in a Java environment. Basic passes them in clear
text (usually encrypted using SSL). The only alternative that won't
pass the password would be Advanced Digest, but I'm not sure you'll be
able to get that to work from Java either. Advanced Digest passes a
hash of the password instead of the password itself.