Don't.
Don't test against arbitrary interfaces, and don't create mocks for them.
Most people seem to see developer (unit) testing as intended for testing nontrivial, individual units of functionality such as a single class. On the other hand, it is also important to perform customer (acceptance/integration) testing of major subsystems or the entire system.
For a web service, the nontrivial unit of functionality is hidden in the classes that actually perform the meaningful service, behind the communication wiring. Those classes should have individual developer test classes that verify their functionality, but completely without any of the web-service-oriented communication wiring. Naturally, but maybe not obviously, that means that your implementation of the functionality must be separate from your implementation of the wiring. So, your developer (unit) tests should never ever see any of that special communication wiring; that is part of integration and it can be viewed (appropriately) as a "presentation" issue rather than "business logic".
The customer (acceptance/integration) tests should address a much bigger scale of functionality, but still not focused on "presentation" issues. This is where the use of the Facade pattern is common--exposing a subsystem with a unified, coarse-grained, testable interface. Again, the web service communication integration is irrelevant and is implemented separately.
However, it is very useful to implement a separate set of tests that actually do include the web service integration. But I strongly recommend against testing only one side of that integration: test it end-to-end. That means building tests that are web service clients just like the real production code; they should consume the web services exactly the way that the real application(s) do(es), which means that those tests then serve as examples to anyone who must implement such applications (like your customers if you are selling a library).
So, why go to all that trouble?
Your developer tests verify that your functionality works in-the-small, regardless of how it is accessed (independent of presentation tier since it is all inside the business logic tier).
Your customer tests verify that your functionality works in-the-large, again regardless of how it is accessed, at the interface boundary of your business logic tier.
Your integration tests verify that your presentation tier works with your business logic tier, which is now managable since you can now ignore the underlying functionality (because you separately tested it above). In other words, these tests are focused on a thin layer of a pretty face (GUI?) and a communication interface (web services?).
When you add another method of accessing your functionality, you only have to add integration tests for that new form of access (presentation tier). Your developer and customer tests ensure that your core functionality is unchanged and unbroken.
You do not need any special tools, such as a test tool specifically for web services. You use the tools/components/libraries/techniques that you would use in production code, exactly as you would use them in such production code. This makes your tests more meaningful, since you are not testing someone else's tools. It saves you lots of time and money, since you are not buying, deploying, developing for, and maintaining for a special tool. However, if you are testing through a GUI (don't do that!), you might need one special tool for that part (e.g., HttpUnit?).
So, let's get concrete. Assume that we want to provide some functionality for keeping track of the cafeteria's daily menu ('cause we work in a mega-corp with its own cafe in the building, like mine). Let's say that we are targeting C#.
We build some C# classes for menus, menu items, and other fine-grained pieces of functionality and its related data. We establish an automated build (you do that, right?) using nAnt that executes developer tests using nUnit, and we confirm that we can build a daily menu and look at it via all these little pieces.
We have some idea of where we are going, so we apply the Facade pattern by creating a single class that exposes a handful of methods while hiding most of the fine-grained pieces. We add a separate set of customer tests that operate only through that new facade, just as a client would.
Now we decide that we want to provide a web page for our mega-corp knowledge workers to check today's cafeteria menu. We write an ASP.NET page, have it invoke our facade class (which becomes our model if we are doing MVC), and deploy it. Since we have already thoroughly tested the facade class via our customer tests, and since our single web page is so simple, we forego writing automated tests against the web page--a manual test using a few fellow knowledge workers will do the trick.
Later, we start adding some major new functionality, like being able to preorder our lunch for the day. We extend our fine-grained classes and the corresponding developer tests, knowing that our pre-existing tests guard us against breaking existing functionality. Likewise, we extend our facade class, perhaps even splitting off a new class (e.g., MenuFacade and OrderFacade) as the interface grows, with similar additions to our customer tests.
Now, perhaps, the changes to the website (two pages is a website, right?) make manual testing unsatisfactory. So, we bring in a simple tool comparable to HttpUnit that allows nUnit to test web pages. We implement a battery of integration/presentation tests, but against a mock version of our facade classes, because the point here is simply that the web pages work--we already know that the facade classes work. The tests push and pull data through the mock facades, only to test that the data successfully made it to the other side. Nothing more.
Of course, our grand success prompts the CEO to request (demand) that we expose the web application to mega-corp's BlackBerrys. So we implement some new pages and a new battery of integration tests. We don't have to touch the developer or customer tests, because we have added no new core functionality.
Finally, the CTO requests (demands) that we extend our cafeteria application to all of mega-corp's robotic workers--you did notice them over the last few days? So, now we add a web services layer that communicates through our facade. Again, no changes to our core functionality, our developer tests, or our customer tests. We apply the Adapter/Wrapper pattern by creating classes that expose the facade with an equivalent web service API, and we create client-side classes to consume that API. We add a new battery of integration tests, but they use plain nUnit to create client-side API classes, which communicate over the web service wiring to the service-side API classes, which invoke mock facade classes, which confirm that our wiring works.
Note that throughout this whole process, we did not need anything significant beyond our production platform and code, our chosen development platform, a few open-source components for automated building and testing, and a few well-defined batteries of tests. Also note that we didn't test anything that we don't use in production, and we didn't test anything twice.
We ended up with a solid core of functionality (business logic tier) that has proven itself mature (hypothetically). We have three separate presentation tier implementations: a website targeted to desktops, a website targeted to BlackBerrys, and a web service API.
Now, please forgive me for the long answer--I tire of inadequate answers and I did not want to provide one. And please note that I have actually done this (though not for a cafeteria menu).