Add vs Set in Memcached
You've pretty much got the answer to your first question already: the intent of ADD is to only work when a key doesn't already exist, while SET is there to update the value, regardless of whether it already exists. If you're familiar with SQL, it's (roughly) like the difference between INSERT queries (ADD) and UPDATE (SET).
In regards to your addendum question, you would use whichever one suits your purpose. I would say that SET would be the more common operation, because it's more common that you just want to say "I want the key foo to have the value bar, and I don't care whether or not it was in there already". However, there would be (less frequent) occasions when it would be necessary to know that a key isn't already in the cache.
An example that comes to mind when ADD would be appropriate is storing sessions in memcache (which, by the way, I don't recommend) -- if you're generating your session IDs randomly (or via hashing), you wouldn't want to create a new session with the same key as an existing one, as this would grant one user access to another user's data. In this case, when you created the session you would use ADD, and if it returned a failure status you would need to generate a new session ID and try again. Updating the session, of course, would then use SET as the user worked their way through your application.
In addition to the answer above by user-id 'womble', please consider the following points as well:
Possibility of a race condition with 'set' as opposed to with 'add'. See below link to an answer by Nick Johnson: https://stackoverflow.com/questions/13234556/using-memcache-add-instead-of-set
If you know 'add' will do, then don't use 'set'. This is to avoid sending data over the network as these are RPC calls. And practically almost all time is consumed by network traffic as opposed to looking for key-value pair in memcache. So if you can avoid network traffic that is best as in that case your response time will be faster.
See Appstats (https://developers.google.com/appengine/docs/python/tools/appstats (by Google)) and to understand point#2 above more, please do watch http://www.youtube.com/watch?v=bvp7CuBWVgA by Guido Van Rossum (@Google)