Why does spin arise in non-relativistic quantum mechanics?
In quantum mechanics, the $\overrightarrow L$ operator and the associated observables $L^2$ and $L_z$ already existed in nonrelativistic QM. The eigenfunctions of $L^2$ and $L_z$ are the spherical harmonics and the eigenvalues are $\hbar^2l(l+1)$ and $\hbar m$ respectively. The values of $l$ can be integer (corresponding to the spherical harmonics) and half integer (corresponding to a divergent solution to the differential equation). Given a value of $l$, the allowed values of $m$ went from $-l$ to $l$ in integer steps, totalling $2l+1$ degeneracy.
You can use the fact that experimental observables are related to the angular momentum operators. In particular, the energy of a dipole in a magnetic field is proportional to $L_z$. When experiments were performed on hydrogen, they observed a number of effects that hinted at electrons having spin. Firstly, electrons occupied hydrogen orbitals (and other atom's orbitals) in pairs. The Pauli exclusion principle forbids electrons from occupying the same state, but if you add a new quantum number with two states, you can explain the behavior of the periodic table. Experiments with Hydrogen in magnetic fields showed that the energy levels diverged. There was the expected behavior of moving charge creating a magnetic dipole. This produced odd splittings in the energy levels (as was expected for moving electrons in spherical harmonic states). But there were also splitting of the energy states which produced an even effect. A last effect worth mentioning and the one that really demonstrates that electrons have intrinsic spin $\frac{1}{2}\hbar$ is that if you send a cathode ray beam through a magnetic field, it will split into two beams in the direction of the magnetic field, indicating that the electron was a magnetic dipole with only two spin states.
These and a few other observations lead physicists to the conclusion that electrons have intrinsic angular momentum of magnitude $\frac{1}{2}\hbar$.
Non-specially relativistic QM is - for a free particle - Galilei invariant. Spin appears as one of the Casimirs of the Galilei algebra when this is represented by essentially self-adjoint operators on its Gårding domain in a separable inf-dim. Hilbert space. The work by Bargmann (1954) and Levy-Leblond in the 1960s should be self-explanatory (for more details, see another answer below).
The relationship between "orbital angular momentum" and "intrinsic spin" is an interesting one.
I will assume you know something about representation theory. A good place to start is here.
Think about the Hamiltonian of the hydrogen atom.
$$\hat H = -\frac{\hbar^2}{2m} \nabla^2 - \frac{e^2}{4 \pi \epsilon_0 r}$$
Discounting spin, the wave function of an electron (in the position basis) is just a function $\psi: \mathbb{R}^3 \to \mathbb{C}$. The group of rotations in three dimensions, $SO(3)$, naturally acts on functions of this form. Namely, for a matrix $R \in SO(3)$, the action is given by
$$U(R) \psi(x) = \psi(R^{-1} x).$$
(The inverse is necessary because $SO(3)$ is not abelian.) In my equation above, $U$ is a map that takes elements of $SO(3)$, which are special orthogonal matrices $\mathbb{R}^3 \to \mathbb{R}^3$, to elements that act on our state space. If we call our state space $\mathcal{H}$, then $U(R) : \mathcal{H} \to \mathcal{H}$. Furthermore $U(R)$ is unitary because $U(R) \psi$ has the same norm as $\psi$.
This is, of course, a representation of $SO(3)$ on our state space. It's not surprising that representation theory is so important on quantum mechanics. State spaces in quantum mechanics are vector spaces. When a group acts on a state space, it therefore acts on a vector space. This is all that representation theory is!
Here is the interesting thing: for all $R \in SO(3)$, we have
$$[\hat H, U(R)] \psi(x) = 0 $$ $$\Rightarrow [\hat H, U(R)] = 0. $$
In other words, the Hamiltonian is invariant under rotations.
Now, $U$ is a representation, but it is not an irreducible representation. We can break up the vector space $\mathcal{H}$ into subspaces such that $U(R)$ acts as an irreducible representation on each subspace. We will call these subspaces $\mathcal{H}_n$.
The fact that $[\hat H, U(R)] = 0$ has two important consequences (which I suppose are not really distinct).
If $\psi$ is a definite energy state with energy $E$, then $U(R) \psi$ is also a definite energy state with energy $E$. This can be seen through the following simple calculation:
$$\hat H U(R) \psi = U(R) \hat H \psi = U(R) E \psi = E U(R) \psi$$
This also means that after time evolution, a state lives in a particular irreducible representation then after time evolution it will still be in that same representation. If a state lives in a particular representation $\psi \in \mathcal{H}_n$ then $U(R) \psi \in \mathcal{H}_n$ as well. That states in a representation after time evolution follows from the fact that time evolution is given by the operators $e^{-i \hat H t / \hbar}$.
$\hat H$ must act as a constant on each $\mathcal{H}_n$. In other words, all the vectors in each irreducible subspace $\mathcal{H}_n$ must all be eigenvectors of $\hat H$ with the same eigenvalue. So all the vectors in $\mathcal{H}_1$ are eigenvectors of $\hat H$ with the eigenvalue $E_1$, all the vectors in $\mathcal{H}_2$ are eigenvectors of $\hat H$ with the eigenvalue $E_2$, etc. This is just Schur's lemma.
You might now be asking yourself, "well that's great, but what are the irreducible representations of $\mathcal{H}$? What are $\mathcal{H}_n?$ The answer is that the irreducible representations of our state space are just the spherical harmonics (multiplied by the appropriate radial function to make them energy eigenstates).
This is not surprising. If you take some linear combination of spherical harmonics of a specific $l$
$$a_1 Y^l_1(\theta, \varphi) + a_2 Y^l_2(\theta, \varphi) + a_3 Y^l_3(\theta, \varphi) + \ldots$$
and rotate the arguments, all that will change are the $a_i$'s! This is what spherical harmonics are. This is the easiest way to see that they are representations of $SO(3)$.
So okay. Lets back up. Representations of our state space break down into these spherical harmonics, which will the the eigenspaces of our energy operator.
It turns out that the irreducible representations of $SO(3)$ can be labeled by an odd number which is the dimension of the representation. For $\mathcal{H}$, each of these irreducible representations is present exactly once with no repeats. The lowest energy eigenspace will be the trivial representation. The next eigenspace up will be 3 dimensional. The next will be 5 dimensional, and so on. You may recognize $1, 3, 5, 7, \ldots$ as the number of electrons in each suborbital of an atom. (Well, multiply them by 2 to account for spin degeneracy!)
Now okay, that explains why representations of $SO(3)$ ought to be important in quantum mechanics. Let me now explain what this has to do with angular momentum.
$$\hat L_j = -i \hbar (\vec r \times \nabla)_j$$
The operator $\hat L^2$ will also commute with $U(R)$. So the story we've spun about what happens when $\hat H$ commutes with $U(R)$ will apply here, too.
But actually, there's more. Not coincidentally, $\hat L_x$, $\hat L_y$ and $\hat L_z$ are the generators of $U(R)$ (in the Lie algebra sense). That is,
$$e^{i \theta \hat L_x / \hbar}$$
is a rotation around the $x$-axis by an angle $\theta$, and so on.
So after all of that exposition, here is what orbital angular momentum has to do with spin: $SO(3)$ itself is just a representation of $SU(2)$. (It is the spin 1 representation.) Therefore, any system with an $SO(3)$ symmetry is going to break up much like it would if it had an $SU(2)$ symmetry. The commutation relations of $\hat L_i$ are the same as for the Lie algebra of $SU(2)$. Long story short: they're just very similar things.
I guess I petered out at the end, but I hope that helped.