First the good news, WCF clients should just work with Java services that use custom SOAP headers.
Now the not so good news, Java proxies generated from the default WCF WSDL won't include the SOAP headers in the object model. The root problem is most Java platforms represent headers in WSDL differently than WCF. In WCF, the body and the headers are defined in different WSDL message elements:
<wsdl:part name="stringBody" element="tns:stringBody" />
<wsdl:part name="IntHeader" element="tns:IntHeader" />
but for most Java platforms, only one message with multiple parts is defined:
<part element="s0:stringBody" name="parameters" />
<part element="s0:IntHeader" name="IntHeader" />
The workaround is to modify the WCF WSDL to mirror the Java-style WSDL (eliminate the OneHeaderIntRequest_Headers message and move the IntHeader part into the OneHeaderIntRequest message in this case). Unfortunately this is a manual process. Now to serve this wsdl requires setting the ExternalMetadataLocation property on the ServiceMetadataBehavior either in a service host or in config.