You could also use Web Services Enhancements (WSE) 3.0 to sign your messages. The nice thing is that everything is built right in, so you won't have to do a whole ton of work.
There's a wide variety of turn-key security options, but it sounds like you would be the most interested in the AnonymousOverCertificate solution. For your implementation, you could define a couple of really simple policy files.
Bear in mind you'll need to use WSE 3.0 on both sides, though. (Client and server sides, that is.)
For more information, check out the link below. It gives a general overview of WSE 3.0.
What's New in Web Services Enhancements (WSE) 3.0