Asynchronous service
Say you have a long running web service (say it reads a large file from the file system and does some processing).
If you set this up as a 'synchronous' web service (using the WCF definition of that), then the calling client will have to wait until the processing completes, and typically this will block on one of the asp.net worker threads while processing completes. For a service with high traffic, this can become problematic.
If you set this up as an asynchronous web service, then what you are saying is that your code is going to delegate some of the long running processing to another thread, or use a non-blocking mechanism, and that this will return at some point in the future (if you are using c# 5.0, then you might want to look at examples of the async and await keywords).
For the example, reading a large file could be done using one of the async ReadFile methods.
This will not block one of the asp.net worker threads, allowing potentially greater throughput.
(There is often some confusion when people refer to making multiple simultaneous calls to the same service (often via AJAX from a web page) - while the calls from the page will typically be made using an asynchronous mechanism in javascript, this is not quite the same as what is described above - I like to keep a distinction between multiple parallel calls and asynchronous calls in my head)
Asynchronous calls
It's also worth noting that you can make an asynchronous call to a service even if that service is not set up to be 'asynchronous'. This is how AJAX calls in javascript will work, e.g.
var jqxhr = $.ajax( "AnyService.svc" )
.done(function() { alert("success"); })
.fail(function() { alert("error"); })
.always(function() { alert("complete"); });
alert("Called");
For this example, you would expect to see 'Called' displayed before 'Success', as this will not wait for the service to return prior to proceeding. The service you are calling does not have to be 'asynchronous'.
Edit
As pointed out in the comments, you can also have a client that calls an 'asynchronous' service in a synchronous manner (i.e. the service will not block worker threads for further requests, but the client will block at that side).