We know that:
Spin structures will exist if and only if the second Stiefel-Whitney class $w_2(M)\in H^2(M,\mathbb Z/2)$ of $M$ vanishes.
Can someone use simple words and logic to show why the above is true?
Note. More precisely, from Wikipedia: André Haefliger found necessary and sufficient conditions for the existence of a spin structure on an oriented Riemannian manifold (M,g). The obstruction to having a spin structure is certain element [k] of $H^2(M,\mathbb{Z}/2)$. For a spin structure the class [k] is the second Stiefel-Whitney class $w_2(M)\in H^2(M,\mathbb{Z}/2)$ of M. Hence, a spin structure exists if and only if the second Stiefel-Whitney class $w_2(M)\in H^2(M,\mathbb Z/2)$ of M vanishes.
A. Haefliger (1956). "Sur l’extension du groupe structural d’un espace fibré". C. R. Acad. Sci. Paris 243: 558–560.
Spin structures and the second Stiefel-Whitney class are themselves not particularly simple, so I don't know what kind of an answer you're expecting. Here is an answer which at least has the benefit of being fairly conceptual.
First some preliminaries. Recall that a real vector bundle of rank $n$ on a space is the same thing as a principal $\text{GL}_n(\mathbb{R})$-bundle (namely its frame bundle) and that principal $G$-bundles are classified by maps into the classifying space $BG$. In particular, a smooth manifold $M$ of dimension $n$ has a tangent bundle which has a classifying map $M \to B\text{GL}_n(\mathbb{R})$. Additional information allows us to reduce the structure group of this classifying map as follows:
Now, what does this have to do with the second Stiefel-Whitney class? First let me tell a simpler story about the first Stiefel-Whitney class. The first Stiefel-Whitney class is a cohomology class $w_1 \in H^1(B\text{O}(n), \mathbb{F}_2)$ giving a characteristic class for $\text{O}(n)$-bundles which vanishes iff those bundles can be reduced to $\text{SO}(n)$-bundles. Why?
One reason is the following. $w_1$ can be regarded as a homotopy class of maps $B \text{O}(n) \to B \mathbb{Z}_2$ (where I use $\mathbb{Z}_2$ to mean the cyclic group of order $2$). Now, it's known that any such map comes from a homotopy class of maps $\text{O}(n) \to \mathbb{Z}_2$, and there's an obvious candidate for such a map, namely the determinant. This gives an exact sequence
$$1 \to \text{SO}(n) \to \text{O}(n) \to \mathbb{Z}_2 \to 1$$
which, after applying the classifying space functor, gives a homotopy fibration
$$B \text{SO}(n) \to B \text{O}(n) \xrightarrow{w_1} B \mathbb{Z}_2$$
exhibiting $B \text{SO}(n)$ as the homotopy fiber of the first Stiefel-Whitney class.
The homotopy fiber of a map between (pointed) spaces is analogous to the kernel of a map between groups; in particular, if $w : B \to C$ is a map of groups, then a map $f : A \to B$ satisfies $w \circ f = 0$ if and only if $f$ factors through a map $A \to \text{ker}(w)$. The same kind of thing is happening here: a classifying map $f : M \to B \text{O}(n)$ satisfies that $w_1 \circ f$ is homotopic to a constant map if and only if it factors up to homotopy through the homotopy fiber $M \to B \text{SO}(n)$.
Now the reason I gave such a sophisticated description of orientations is that the story for spin structures is completely parallel. Namely, the second Stiefel-Whitney class is a cohomology class $w_2 \in H^2(B\text{SO}(n), \mathbb{F}_2)$ which can be regarded as a homotopy class of maps $B \text{SO}(n) \to B^2 \mathbb{Z}_2$. You can produce such classes by applying the classifying space functor to a homotopy class of maps $\text{SO}(n) \to B \mathbb{Z}_2$, or equivalently a cohomology class in $H^1(\text{SO}(n), \mathbb{F}_2)$, and there's a natural candidate for such a class, namely the cohomology class classifying the nontrivial double cover $\text{Spin}(n) \to \text{SO}(n)$. This also turns out to imply that we get a homotopy fibration
$$B \text{Spin}(n) \to B \text{SO}(n) \xrightarrow{w_2} B^2 \mathbb{Z}_2$$
exhibiting $B \text{Spin}(n)$ as the homotopy fiber of the second Stiefel-Whitney class, and if you believe this then it again follows from the universal property of the homotopy fiber that a map $f : M \to B \text{SO}(n)$ lifts to a map $M \to B \text{Spin}(n)$ iff $w_2 \circ f$ is homotopic to a constant map.
(This homotopy fibration is a "delooping" of the more obvious homotopy fibration $B \mathbb{Z}_2 \to B \text{Spin}(n) \to B \text{SO}(n)$ coming from the short exact sequence $1 \to \mathbb{Z}_2 \to \text{Spin}(n) \to \text{SO}(n) \to 1$.)
This argument can be continued all the way up the Whitehead tower of $B \text{O}(n)$; the next step is a string structure, etc.