If you're being any kind of RESTful, think in terms of your service providing access to your resources, but instead of exposing direct access to those resources, you return representations (e.g. XML and/or JSON based) of those resources.
Name, define and document "media types" for the resource representations that your service returns. E.g. "application/vnd.blah+json". You don't have to register these media types publicly, they can be private to your service. But they do
need to be documented, and that documentation needs to be made available to clients.
Now consider rules 3 and 5 in the bullet-point list in this (in)famous blog entry by Roy Fielding:-
Actually, consider all the rules given there, but 3 and 5 seem most pertinent to this dicussion.
Rule 3 starts: "A REST API should spend almost all of its descriptive effort in defining the media type(s) used for representing resources"
Rule 5 starts: "A REST API should never have “typed” resources that are significant to the client."
Even if you don't want to be totally RESTful, these are rules (aka constraints) that are useful for many kinds of API/service that are exposed over HTTP/the web.
I find it's useful to follow REST rules, even if I call my service a "Web API" rather than a "REST service".
You asked how a client would know about changes to the Contact class... well, I recommend the "RESTful Web Services Cookbook" which has a whole section on extensibility and versioning.