Before you dig into REST, here are some terms you really need to grasp:
Resource - The things/data you want to make available in your API (in your case a "User")
URI - A universally unique ID for a resource. Should mention noting about the method being performed (e.g. shouldn't contain "add" or "delete"). The structure of your URI however doesn't make your app any more or less RESTful - this is a common misconception.
Uniform Interface - A fixed set of operations you can perform on your resources, in most cases this is HTTP. There are clear definitions for the purpose of each of these HTTP methods.
The most unrestful thing about your URIs as they are right now is that they have information about the operation being performed right in them. URIs are IDs and nothing more!
Let's take a real world example. My name is Nathan. "Nathan" could be considered my ID (or in restful terms URI, assuming I'm the only "Nathan"). My name/ID doesn't changed based on how you would like to interact with me - e.g. My name wouldn't change to "NathanSayHello" when you wanted to greet me.
Its the same for REST. Your user IDed by http://api.domain.com/users/1 doesn't change to http://api.domain.com/users/1/update.xml when you want to update that user. The fact that you want to update that user is implied by the method you're using (e.g. PUT).
Here is my suggestion for your URIs
# Retrieve info about a user
GET http://api.domain.com/users/<id>
# Retrieve set all users
GET http://api.domain.com/users
# Update the user IDed by api.domain.com/user/<id>
PUT http://api.domain.com/users/<id>
# Create a new user. The details (even <id>) are based as the body of the request
POST http://api.domain.com/users
# Delete the user ID'd by api.domain.com/user/<id>
DELETE http://api.domain.com/users/<id>
As for your questions:
Use PUT and DELETE if you want to use HTTP correctly. Sometimes people overload POST but its usually a bad idea due to the idempotent nature of POST.
Remove "add" altogether. Use HTTP's Content-Type header for specifying the mime-type of posted data.
Are you referring to the version of your API or the version of the resource? ETag and other response headers can be used to version the resources.
Many options here. Basic HTTP Auth (easy but insecure), Digest Auth, custom auth like AWS. OAuth is also a possibility. If security is of main importance, I use client side SSL certs.