I'm using a web reference generated from a .wsdl file. I've also examined the Amazon web service example but couldn't get it working. Enclosed is an example of the soap request.
<soap:Envelope xmlns:soap="http://schemas.xmlsoap.org/soap/envelope/">
<soap:Header>
<wsse:Security
xmlns:wsse="http://schemas.xmlsoap.org/ws/2002/07/secext">
<wsse:BinarySecurityToken valueType="wsse:X509v3"
encodingType="wsse:Base64Binary" id="X509Token">
MIIEZzCcA9cgwaABQfd86afd2g...
</wsse:BinarySecurityToken>
<ds:Signature xmlns:ds="http://www.w3.org/2000/09/xmldsig#">
<ds:SignedInfo>
<ds:CanonicalizationMethod>
Algorithm="http://www.w3.org/2001/10/xml-enc-c14n#"/>
</ds:CanonicalizationMethod>
<ds:SignatureMethod Algorithm="
http://www.w3.org/2000/09/xmldsig#rsa-sha1"/>
<ds:Reference URI="#MsgBody">
<ds:Transforms>
<ds:Transform
Algorithm="http://www.w3.org/2001/10/xml-exc-c14n#"/>
</ds:Transforms>
<ds:DigestMethod
Algorithm="http://www.w3.org/2000/09/xmldsig#sha1"/>
<ds:DigestValue>DJbchm5gk...</ds:DigestValue>
</ds:Reference>
</ds:SignedInfo>
<ds:SignatureValue>LyLsF0pi4wPu...</ds:SignatureValue>
<ds:KeyInfo>
<wsse:SecurityTokenReference>
<wsse:Reference URI="#X509Token"/>
</wsse:SecurityTokenReference>
</ds:KeyInfo>
</ds:Signature>
</wsse:Security>
</soap:Header>