First thing to realise is that a new version of a service can be seen as a new service. Alike  but different. The question then changes to "how to minimise duplication if services are similar".
As for versioning, you can use the namespace declaration (e.g. targetNamespace="mynamespace/1.0") or a <version>1.0</version> tag in (or version="1.0" attribute on) the root node of the types used for request/response messages).
Using the namespace most likely means that one implementation can only serve one version of the service. If you want a certain implementation to serve, say, version 1.0-1.3 and another 1.3+, than you will likely use the <version/> method (or @version), since in that case there is only one namespace. Implementations can than internally decide wether to process or deny based on the value of <version/>. 
In a more hybrid service landscape, you can use the <version/> method to create a proxy implementation that relays to services that use the targetNamespace method. Better still would be using a UDDI for this, if you have one at your disposal.
Please consider backwards compatibility of your changes. Adding an operation, as you suggest, is fully backwards compatible. If you have a client X on version 1.0, and add an operation to you server (now 1.1), X can still call the server because all the operations X knows about are still available. (Provided you did not change the namespace to reflect the version that is (use <version/>.) The (absence of) backward compatibility of an interface is usually reflected in a changed major version number (e.g. 1.1 ->  2.0), which may cause you to realize that you could do major changes with the namespace and minor ones with a <version/> tag.
Have fun, this is interesting stuff to be working on!