As was correctly indicated by @whpowell96, for a physicist a vector is not just an element of a linear space, but rather a pair $(\text{transformation group}, \text{element of a vector space on which the group acts})$, and the group must act on the space in a particular manner (mathematically speaking, I suppose, the action must be by the fundamental representation of the group). This means, in particular, that if a physical quantity is a vector depends not only on the quantity itself, but also on the transformation group you are concerned with.
Take, for instance, proper rotations of $\mathbb{R}^3$ (i.e. the regular rotations you can perform on a physical object), which form a group called $SO(3)$. Consider the speed $\vec{v}$ of a charged object with a charge $q$ moving in space, the constant external magnetic field $\vec{B}$ acting on the object, and the Lorentz force ${\vec{F}}$ in which this action results. The speed, the field and the force all have three components in a particular coordinate system, $\vec{v}=(v_1, v_2, v_3)$, $\vec{B}=(B_1, B_2, B_3)$, $\vec{F}=(F_1, F_2, F_3)$. The force is given by the equation
$$\vec{F}=q(\vec{v} \times \vec{B})$$
where $\times$ is the vector product.
Suppose we rotate in space, our rotation being described by an orthogonal matrix $R$ with unit determinant (i.e., a proper rotation matrix): first we measured all quantities with respect to a set of three orthogonal vectors $\vec{e_1}, \vec{e_2}, \vec{e_3}$, now we want to take measurements with respect to a new triple of orthogonal vectors of the same length, but differently oriented: the new (basis) vectors are $Re_{1}$, $Re_2$, $Re_3$. The speed of an object is measured as change in position per unit time: in old coordinates the object has moved by $\Delta x_{1} \cdot e_{1} + \Delta x_{2} \cdot e_{2} + \Delta x_{3} \cdot e_{3}$.
Express the new coordinates through the old:
$${e_i}' = Re_i \iff e_{i} = R^{-1}{e_i}'$$
The key conservation is that the displacement of the object hasn't changed, the way we describe it has, that is what's meant by the phrase "a vector is invarinat with respect to a transformation" - the transformations describe the way we observe the universe, in this particular example, our spatial orientation. In different coordinate systems we describe differently the same objects. So the displacement vector in the old coordinates equals the displacement vector in the new coordinates:
$$\Delta x_{1}'\cdot \vec{e}'_{1} + \Delta x_{2}'\cdot \vec{e}'_{2} + \Delta x_{1}'\cdot \vec{e}'_{1} = \Delta x_{1}\cdot \vec{e}_{1} + \Delta x_{2}\cdot \vec{e}_{2} + \Delta x_{3}\cdot \vec{e}_{3}$$
Since we know how to express the new basis vectors in terms of the old, we can determine the new coordinates:
$$\sum_{i=1}^{3} \Delta x_{i} \cdot \vec{e}_{i} = \sum_{i=1}^{3} \Delta x_{i} \cdot R^{-1}\vec{e}'_{i}= \sum_{i=1}^{3} \Delta x_{i}' \cdot e'_{i}$$
Note that $R^{-1}e_{i}' = \sum_{k} R^{-1}_{ki}e_{k}'$ where the first index enumerates the row, and the second enumerates the column. Physicists are lazy, so instead of writing down sums they usually assume all indices that repeat twice in a monomial are summed over, and write down such an expression as
$$\sum_{k} R^{-1}_{ki}\vec{e}_{k} := R^{-1}_{ki}\vec{e}_{k}$$ - that's called Einstein's convention, and I will use it form now on. The summation over a repeated pair of indices is called contraction.
The previous expression is then written down as
$$\Delta x_i \cdot \vec{e}_{i} = \Delta x_{i} \cdot R^{-1} \vec{e}'_{i} = \Delta x_{i} \cdot R^{-1}_{ki}\vec{e}'_{k} = \Delta x_{i}' \cdot \vec{e}'_{k}$$
and now it is easy to see that the new coordinates of the displacement vector $\Delta x_{i}'$ are given by the sum $\Delta x_{i} R_{ki}^{-1}$. First, we've expressed new coordinates in terms of old, second, since $R_{ki}$ are just numbers, we can rewrite the sum as $R_{ki}^{-1} \Delta x_{i}$ (this is a general thing: in Einstein notation multipliers with indices inside monomials become commutative), third, we note that $R_{ki}^{-1}\Delta x_{i}$ is matrix multiplication $R^{-1}\Delta x_{i}$. This is, of course, a familiar fact from linear algebra I: if a basis is changed by a linear transform $R$, the coordinates of vectors change by $R^{-1}$. The magnetic field components, of course, change in the same manner, as well as the components of the Lorentz force, so we say that all three are $SO(3)$-vectors: because their components change like the components of the coordinate vector when we rotate our coordinate system. The tuple $(\text{#bananas}, \text{#pears}, \text{#apples})$ is not an $SO(3)$-vector: the number of bananas, pears and apples does not change when we rotate, and bananas, apples and pears do not transform one into another. It is a tuple of $SO(3)$-scalars.
Now, suppose we look at the world through a looking glass, and want to describe the same system. The coordinate transform corresponding to this observation method is reflection with respect to a plane; such reflections are described by so-called Hausholder matrices. It is easy to see that the reflection with respect to a plane is linear, orthogonal (it conserves lengths of vectors), but is not described by a proper rotation: you can't rotate your right hand in such a way that it would look like a left hand. Reflections thus constitute a part of a larger group, $O(3)$, the group of all orthogonal transformations, of which $SO(3)$ is a subgroup. One can also show that all orthogonal transformations are combinations of reflections with respect to one of coordinate axes and of proper rotations.
So, how do the three quantities change under reflections? Take, for instance, reflection with respect to the $x$ axis: $P_x: (\vec{e}_{1}, \vec{e}_{2}, \vec{e}_{3}) \rightarrow (-\vec{e}_{1}, \vec{e}_{2}, \vec{e}_{3})$. It is easy to see that the $x$-component of the coordinate vector changes its sign. Remember that Lorentz force is described as $\vec{F}= q\cdot [\vec{v}\times \vec{B}]$. When we reflect two vectors $\vec{B}$ and $\vec{v}$ with respect to a plane, the orientation of the pair $(\vec{B}, \vec{v})$ changes, if the vectors are not very special (are not both in the reflection plane, and are not collinear). According to the Lorentz law, the force must now act in the direction opposite to the one really observed. Hence, we should either change the Lorentz law, or state that one of the quantities involved in its calculation changes the sign when mirrored. The displacement vector, evidently, does not change the sign, and, using the Coulumb law, one can check that this is not the case for the electric charge, either. We must conclude it is magnetic field that changes its sign; besides, one can consider the magnetic field generated by a loop of electric current (see the Wikipedia illustration). Therefore, we conclude that velocity and Lorentz force are $O(3)$ vectors, while magnetic field is not, despite being $SO(3)$-vector. Such a kind of $SO(3)$-vectors that change sign under reflection is called "pseudovectors". In particular, the vector product of a pair of $O(3)$ vectors is always a pseudovector: take, for instance, the angular momentum vector, and observe how it changes when you look at a rotating object through a mirror.
In special relativity, even velocity is not a vector anymore: if you want to describe the universe moving with a speed close to the speed of light relative to it, or describe objects which are themselves moving very fast with respect to you (which is, of course, the same thing), you need to work with a four-dimensional vector called 4-velocity, which is a vector with respect to a group of transformations called the Lorentz group, or $O(3,1)$; the Lorentz group contains $O(3)$ as a subgroup, the first component of the 4-velocity can be thought of as "the speed of moving forward in time". It is similar to the rotation group in the sense that it consists of transformations of spacetime that conserve a certain kind of "length" of vectors (called interval), but this relativistic "length" can be zero or even negative, since vectors oriented "along the time coordinate" contribute to this "length" with a negative sign.
The usual rotations of coordinate frame with zero speed relative to the objects you describe are given by transformations of the form
$$1 \oplus SO(3)$$
while so-called Lorentz boosts, that describe how you observe the universe moving with a nonzero speed with respect to it, are given by a $4 \times 4$ matrix that "mixes up" the time and the spatial components of the 4-vector. Another example of a 4-vector is the vector with components $A^{\nu} = (\phi, \vec{A})$, where $\vec{A}$ is the vector potential, a quantity such that $\nabla \times \vec{A} = \vec{B}$, and $\phi$ is the elecrtic potential. If you want to describe the 4-potential in a moving reference frame, you multiply the 4-potential in the still reference frame by the boost matrix $\Lambda^{\mu}_{ \ \nu}$, which is a function of 3-velocity, and obtain the components of the 4-potential in the moving frame:
$$A'^{\mu} = \Lambda^{\mu}_{ \ \nu}A^{\nu} \text{ Remember the Einstein's convention}$$.
The $\vec{E}$ electric field $O(3)$-vector and the $\vec{B}$ magnetic field $O(3)$-pseudovector are not vectors under the Lorentz group: they are actually components of the electromagnetic field tensor: a $4 \times 4$ matrix $F_{\mu \nu}$, which changes under Lorentz transformations according to the tensorial transformation law:
$$F_{\mu \nu}' = \Lambda^{\mu'}_{ \ \mu}\Lambda^{\nu'}_{ \ \nu}F_{\mu' \nu'}$$. In general, physicists describe tensors as objects with multiple indices ("$n$-dimensional matrices"), the components of which transform under a group action by contracting the transformation matrices by one of the indices with all indices of the tensor. Scalars are tensors of rank 0, vectors are tensors of (total) rank 1, matrices are tensors of (total) rank 2, and so on. Generally, there is more then one type of tensors per each total rank: for example, tensors on the Lorentz group can have two type of indices, "higer" and "lower", which correspond to "contravariant" and "covariant" quantities, but that is a topic for a different discussion. For $SO(3)$-tensors, there is only one type of indices.