Why is velocity a vector? Velocity has a magnitude and a direction and thus it is considered a vector.
But from linear algebra perspective, a vector is an element of a vector space.
A set of mathematical objects can be a vector space if they follow some conditions. One of the conditions is that if we add two vectors we must get another vector from the set.
Which set of vectors should I take as the vector space?
If car A has a velocity $\vec{v}$, can we add this velocity to the velocity of car B and get another vector?
is the velocity of the car B in the same vector space?
What is the physical significance of such addition of vectors?
 A: In general, whenever you add any two vectors from the same vector space, then you do get a vector that is also a member of this vector space.
The same can be said about velocity vectors.
Velocity vectors also form vectors in a tangent vector space, the set of all three dimensional spatial vectors (or however many dimensions $n$ you're working in) tangent to position curves in ${\mathbb R}^n$.
So if you take two velocity vectors from this space, and add them together, the result is still a vector in the same vector space, completely analogous to your above example from linear algebra$^1$.
For any vector space $\mathbb V$, vector addition can be thought of as the map  $+ : \mathbb V \times \mathbb V\rightarrow \mathbb V$ , that maps two vectors ${\bf u, v} ∈ \mathbb V$
to their sum ${\bf {u + v}} \in \mathbb V$
For your example of adding the velocity of one car to that of another car, while it may make sense mathematically, it does not really make sense physically since the velocity of one car is independent of the other car.
However, if you consider that, for example, two forces are operating on the one car so that one pushes the car with velocity $\bf v$ and the other with velocity $\bf u$, then the car will have a resultant velocity $\bf u+v$, where the vectors $\bf u$, $\bf v$ and $\bf u+v$ are all members of the same vector space.
$^1$Note that velocity vector addition in relativity is not so straight forward, since simple linear addition no longer holds, and time is treated on equal footing as space. Points in space (spacetime) are defined by position four-vectors. In this case, velocity vectors belong to the space of tangent four-vectors, that are tangent to points on curves in spacetime.
A: 
But what does it mean to add velocities?

It seems this is what your are struggling with. To understand intuitively what it means to add velocity vectors, consider a small example.
Let us say, there is a cannon which fires balls at 300 km/hr at an angle of 30 degrees to the horizontal.
And you put it on a car that is travelling along a horizontal ground at 100 km/hr.
To get the resultant velocity of the ball when it is fired, we do a vector addition i.e. we add the velocity vector of the cannon ball to the velocity vector of the car.
A: There are already many answers. Some of them mention the composition of velocities as an example of the vector sum of velocities. That is misleading. If things would be so simple, there would be no room for the relativistic composition of velocities, which is not a vector sum. In order to establish the correct correspondence between the physical concept of velocity and the properties of a vector space, one has to be very clear about what are the objects that one would like to consider elements of the vector space.  It is meaningless to speak about velocity without specifying velocity of what.
Velocity is a physical property of a physical system. More precisely, we say that a point-like object has velocity $\bf v$ at a time $t$, if ${\bf v}= \frac{{\mathrm d}{\bf r}}{{\mathrm d }t}$, where $ {\bf r}(t)$ is the trajectory of the body as a function of the time.
Actually, such a definition already enables us to say that velocities are elements of a vector space, inheriting the vector space structure from that of the positions (or displacements).
However, we could investigate the algebraic structure of the possible set of velocities independently. In such a case, we need to find an operative procedure to give a velocity to a body and to compare different velocities of the same body. The key point is that the sum we need must be the sum of two velocities of the same body. This excludes the composition of velocities in different reference frames. We need the properties of velocity in one frame, before asking about changes with the reference frame.
The definition allows mapping any velocity of a body to the linear approximation of the displacements d${\bf r}= {\bf v}{\mathrm d}t $. A simple way to provide a physical mechanism to sum a velocity ${\bf v}'$ to a velocity ${\bf v}$  is through an impulsive force, like in the case of an elastic collision with another body: if we know that an impulsive force $\bf F_1$ on a body at rest will produce a  velocity $\bf v_1$ and another impulsive force $\bf F_2$ will produce velocity $\bf v_2$, we can define the sum  $\bf v_1+v_2$ as the velocity resulting from the simultaneous presence of the $\bf F_1$  and $\bf F_2$.
Starting with this definition of the sum of velocities, we are left with the task of verifying by experiments that it satisfies the corresponding requirements for a vector space (existence of the neutral element, the existence of the inverse, and the other axioms of a vector space.
A: If we want to be mathematically precise, just saying "velocity is a vector" doesn't cut it.
The definition of velocity is as the time derivative of position. In mathematical terms, this means - regardless of whether we think of position as a point in $\mathbb{R}^n$ or a more general manifold where position itself is not a vector - velocities are tangent vectors to curves $x(t)$ in our position space. In general, you can add two tangent vectors at the same point because they are vectors in the same tangent space, but you cannot add "velocity of car A" to "velocity of car B" unless the two cars are currently colliding and hence these two vectors live at the same point.
Adding two velocities at the same point is just a way to express that it is equivalent to say "This thing is moving at $\sqrt{2} \frac{\mathrm{m}}{\mathrm{s}}$ northwest" and "This thing is moving at $1\frac{\mathrm{m}}{\mathrm{s}}$ north and it is moving at $1\frac{\mathrm{m}}{\mathrm{s}}$ west" - the "and" there corresponds to addition.
A: Interesting question. I will re-phrase the question as "Is there velocity algebra?" Can I add velocity vectors in a physically meaningful way? There is obviously a force algebra since I can add force vectors, so why not velocity vectors.
Quick Answer. The answer is no because velocity vectors alone are not enough to describe the motion of a rigid body. The motion of body is described by a rotation axis, the speed of rotation and any parallel velocity along the rotation axis (Chasle's Theorem).  To add motions you need to resolve the velocity at a common point in space.
A related restriction occurs with force vectors since you can only add them if their tails are on the same point (using the parallelogram rule).
The exception to the above rule is when there is only pure translation, such as a person walking on a speedy train.
You can however add velocities when you consider a vector that contains both the linear and angular parts of velocity. Such a vector has 6 components in 3D and it is called a twist. On a plane such a vector has 3 components.
I want to prove to you that you can perform algebra with twists, in fact this is how most kinematics of robotic mechanisms is modeled.
The motion of the end effector is just the sum of all the relative twists on each joint
$$ \boxed{ \boldsymbol{t}_{\rm end} = \sum_i^n \boldsymbol{t}_i }$$
The above is an addition of velocity (twists).
A Simplified Detailed Example
Considering only planar motions simplifies things, and allows us to visualize any rotation axis as a point on the plane.
Here two identical bodies #1 and #2 are pinned, each with relative rotational speed of $\dot \theta_1$ and $\dot \theta_2$. The root pin is at point A, the relative pin at B and the end point of interest at C.

The velocity of each particle on a body as you move away from the pivot varies linearly up to point B, and then again linearly by with a different rate up to point C. These are the dashed blue lines you see above and the vertical arrows are the velocity vectors at B and C respectively.
Obviously you cannot just add the velocities to state $v_C = v_A + v_B$, but you can add the rotational velocities.
Here the rotational velocity of the bodies are
$$\begin{aligned}
 \omega_1 & = \dot \theta_1 & & \text{link #1} \\
 \omega_2 & = \omega_1 + \dot \theta_2 & & \text{link #2} \\
\end{aligned}$$
Let us assign the out of plane vector $\hat{z} and bring the above in vector form
$$\begin{aligned}
 \vec{\omega}_1 & = \hat{z} \dot \theta_1 & & \text{link #1} \\
 \vec{\omega}_2 & = \vec{\omega}_1 + \hat{z} \dot \theta_2 & & \text{link #2} \\
\end{aligned}$$
And this is angular  velocity vector addition. But what about linear velocities? Here is what you do:
What is the linear velocity of #1 at B? $$ \vec{v}_B = \vec{\omega}_1 \times \vec{ \ell}$$
And what is  the relative linear velocity of #2 at B? Well it is zero since the two bodies much match speed at the joint. So the velocity of #2 at B is also $\vec{v}_B$ which makes the velocity on the end to be $$ \vec{v}_C = \vec{v}_B + \vec{\omega}_2 \times \vec{\ell} $$
Or you can directly find the velocity at C using vector addition for velocities. Consider $\vec{v}_C$ as the addition of two vectors at a common location, the point C.

The first velocity vector is that of body #1 if it extended out to point C
$$ \vec{v}_{C1} = \vec{\omega}_1 \times 2 \vec{\ell} $$
The second velocity vector is that of the relative joint velocity also extended out to point C
$$ \vec{v}_{C2} = \hat{z} \dot{\theta}_1 \times \vec{\ell} $$
and now we can add velocity vectors
$$ \boxed{ \vec{v}_C = \vec{v}_{C1} + \vec{v}_{C2} } $$
The above is interpreted as, the velocity of body #2 at any point, equals the velocity of body #1 at the same point plus the relative velocity between the two bodies also at the same point.


*

*Related wiki article Relative Centre of Rotation Theorem.


If two planar rigid bodies are in contact, and each body has its own distinct center of rotation, then the relative center of rotation between the bodies has to lie somewhere on the line connecting the two centers.

It is known the linear combination of two points is a point somewhere on the line that connects the points. The above rule is exactly that, as each twist is a point in space for its center of rotation, and the addition of two twists is a linear combination $\boldsymbol{t}_{\rm rel} = \boldsymbol{t}_B - \boldsymbol{t}_A$
A: From the linear algebraic perspective, the resultant vector need not have a physical interpretation in terms of the constituent vectors, it just needs to be some velocity vector (i.e. something could concievably have such a velocity). However, there can in fact be a physical meaning to summing velocities. Consider for example a person, Bob, running on the deck of a moving ship. Bob's velocity with respect to the water will be $\vec{v}_\text{Bob-water}=\vec{v}_\text{Bob-ship}+\vec{v}_\text{ship-water}$.
Things get a bit more complicated in relativity, where velocities don't sum like above. In order to keep everything below the speed of light, velocities are combined using the relativistic velocity-addition formula. So indeed we do not necessarily have the sum of physical velocities being another physical velocity. This is clarified in more sophisticated treatments of relativity, where instead of the "3-velocity" $\vec{v}$ we consider "4-velocity", given (in flat spacetime) by $$V=\gamma(c,\vec{v}).$$ This describes an object's velocity in spacetime by including a "velocity in time" as the $0^\text{th}$ component. These are actually all unit vectors with Minkowski norm $V^2=\eta_{\mu\nu}V^\mu V^\nu=c^2$ and so it is not surprising that $V\neq V_1+V_2$ for any choice of $V_1,V_2$. The space in which the velocity vectors reside is simply the space of 4-vectors tangent to a particular point in spacetime (known as a tangent space), which is a vector space.
A: Intuitively, you can view it like this. Imagine you are driving a car and you are in a curvy road. Evidently, as you transit through the road, you must be changing direction, and you must traveling at a certain rate. It is easy to see from this change in direction that a single number is not sufficient for describing the motion of your car.
Velocity is a pointer that tells you where the particle is going, and to what rate it is going there. This is expressed as $$\vec{v}=\frac{\mathrm{d} \vec{r}}{\mathrm{d} t},$$ where $\vec{r}$ is the position vector of the particle. While adding the velocities of two independent cars often has no physical meaning, it is not describing the motion of anything, but if has for some reason to consider the cars as a single system, and they may be assumed to have the same mass, the centre of mass of the system is $$\vec{R}_{\mathrm{cm}}=\frac{\vec{r}_{\mathrm{car,A}} + \vec{r}_{\mathrm{car,B}}}{2},$$ the velocity of the centre of mass may be found differentiating this relation, $$\vec{V}_{\mathrm{cm}}=\frac{\vec{v}_{\mathrm{car,A}} + \vec{v}_{\mathrm{car,B}}}{2}.$$ Hope this might give the OP an insight about what adding velocities means.
A: The better way to think of vectors is, as you point out, that they are elements of a vector space. In this case, the vector space that velocity "lives" in is $\mathbb{R}^3$, "times" some appropriate unit, with the usual addition and scaling operations.
Vectors are not defined by the properties of "having magnitude and direction", contrary to what you write: rather, vectors are a useful mathematical construct that let us encode information about magnitude and direction simultaneously into a single package that we can then manipulate in useful and intuitive ways.
In particular, any vector in $\mathbb{R}^3$ can be represented as an arrow from the origin to a point. This origin is not the origin of space, but rather an origin you can put wherever you need to "use" the vector, and the arrow is to then be understood as pointing in the encoded direction, while the length is the encoded magnitude. In mathematical formalism, a vector in the vector space is given by a triple of real numbers:
$$\mathbf{v} := \langle v_x, v_y, v_z \rangle$$
and we define its magnitude to be
$$||\mathbf{v}|| := \sqrt{v_x^2 + v_y^2 + v_z^2}$$
and its "direction" by the spherical angles
$$(v_\theta, v_\phi) := \left(\cos^{-1}\left(\frac{\sqrt{v_x^2 + v_y^2}}{v_z}\right), \tan^{-1}\left(\frac{v_y}{v_x}\right)\right)$$
That is, we specify "decoding algorithms" that let us extract the relevanat information from the coded tuple, which are based on geometry: understanding the tuple elements as coordinates, these follow from the Pythagorean theorem and trigonometry.
Now to understand the reason velocity is a vector, we have to go to the definition. The definition is the derivative of position:
$$\mathbf{v}(t) := \left[\frac{dX}{dt}\right](t)$$
However, here's the trick: Position, $X(t)$, is not a vector. Rather, it is a point. Points are also represented by triples in $\mathbb{R}^3$, but the semantics are different: if you like, points and vectors are different "data types" (something we can make precise using typed language to build our maths in). In particular, a point represents a location in actual space. The structure points form, at least in Euclidean geometry, which is what elementary mechanics takes place in, is what is called an affine space. We cannot add points, but we can subtract them: and the subtraction of two points $X_1$ and $X_2$ yields a vector. That is, $X_2 - X_1$ has "data type" $\mathrm{Vector}$, not data type $\mathrm{Point}$. Semantically, this vector encodes the distance you have to travel to go from $X_1$ to $X_2$ when moving in a straight line, and the direction you have to face to accomplish that movement.
And velocity, as the time derivative of position, is defined by a difference quotient ...
$$\left[\frac{dX}{dt}\right](t) = \lim_{\Delta t \rightarrow 0} \frac{X(t + \Delta t) - X(t)}{\Delta t}$$
... and you can see in the numerator, we have
$$X(t + \Delta t) - X(t)$$
... a difference of positions, i.e. of points! And what kind of object is that? Thus, what is velocity?
A: In relativity, velocity vectors do not form a vector subspace. I nuance this, and explain what I mean, in the following.
Consider Minkowski spacetime with the usual coordinates $(t,x,y,z)$, and a "stationary" observer $n^\mu = (1,0,0,0)$. A velocity as measured in this observer's reference frame is a vector $\mathbf v$ which is orthogonal to $\mathbf n$, meaning $n_\mu v^\mu = 0$. (Hence it is spatial, or the zero vector.) For objects moving slower than light, we have $v_\mu v^\mu < 1$ (using $c = 1$), and I take this as a definition of "velocity" for the purposes of this answer. These $\mathbf v$ are vectors in the sense of being elements of Minkowski space, which is a 4-dimensional vector space (plus extra structure), however they do not form a vector subspace thereof.
Consider the relative velocity $(0,2/3,0,0)$, which describes movement at 2/3 the speed of light in the $x$-direction. Summing this vector with itself, or multiplying by the number 10 say, returns vectors which do not lie within our set of velocities.
However there are other natural structures you can define on "The 3-Velocity Space", as Tsamparlis calls it (2019, $\S6.5$, $\S15.4.3$). He defines a certain Riemannian metric on it, for which it becomes a 3-dimensional manifold of constant negative curvature. I guess you could probably define a group structure, corresponding to a relativistic composition of velocities -- which is not the vector addition inherited from Minkowski space. This would make it a Lie group, so not a vector space, but still a nice object. This has likely been done already. Tsamparlis says certain results "have been around for a long time".
A: 
If car A has a velocity v⃗, can we add this velocity to the velocity of car B and get another vector? Is the velocity of the car B in the same vector space? What is the physical significance of such addition of vectors?

Adding these vectors may be mathematically defined, if and only if you stipulate that they indeed belong to the same vector space. Which in reality they don't.
The car A has a velocity with it's own vector space. The car B has a velocity with its own vector space. $A+B$ is therefore invaild.
However if you measure velocity A and use the position of the car B as the point of reference then you obtain a yet another vector space, members of which are the relative velocity of the two cars.
Just because the vector spaces are mathematically identical doesn't mean they are the same.
