This week's book giveaway is in the OCAJP 8 forum. We're giving away four copies of OCA Java SE 8 Programmer I Study Guide and have Edward Finegan & Robert Liguori on-line! See this thread for details.
The usual way to manipulate the headers of a SOAP message using Java is through an object implementing the SOAPHeader interface.
After some calls, you will get an object implementing the SOAPElement interface. This interface extends the DOM interfaces Element and Node, thus you can add a DOM node to a SOAPHeader object.
Then you need to transform the JAXB object into a DOM object, before you can add it to the SOAPHeader object. Take a look at the JavaSE 6 API documentation for javax.xml.bind.Marshaller on how to do this.
An alternate route is to manipulate a string representing the XML message. This is not the solution I would prefer, but it may reduce the amount of code you have to write.
A third alternative is using Groovy, which is good at XML manipulation, or some additional framework. If you have restrictions imposed on you, this may not be a viable option.