Consume a WebService written in Java by our provider from our vb.net App

I'm trying to consume a WebService written in Java by our provider from our vb.net App. When it's time to communicate, I get this:
WSDoAllReceiver: Incoming message does not contain required Security header
Since a week, I'm trying to find out how to add security header to a SOAP message. I have read many articles about this but none of the suggested code works for me.
I looked around and this seems to be a rather asked question. I wonder if I can get some help here, some pointers, some working code , to get me started.

Note: I am using VS 2010.
Thanks