Vector Rotation in 3D Given:  


*

*Two points: ($x_1$, $y_1$, $z_1$), ($x_2$, $y_2$, $z_2$)  

*A vector that is parallel to the $x$-axis and points to ascending numbers (intuitively stated, the vector points 'East').


I am hoping for a formula that tells me how many degrees I need to rotate the given vector around:  
1) the x-axis
2) the y-axis
3) the z-axis  
... in order to have the vector become parallel with the line that goes through the given points.
 A: It's not quite clear whether these are three separate questions, or one question with three consecutive rotations.
If these are three separate questions, you only have one free parameter in each case, the rotation angle, but a three-dimensional manifold of directions to cover, so it won't work.
If these are three consecutive rotations, the first one won't change the direction of the vector since it's parallel to the $x$ axis, but as Tony rightly pointed out, the remaining two rotations are enough to rotate it in the direction you want.
You can get the combined effect of rotations 2 and 3 by successively multiplying a vector $(1,0,0)$ along the positive $x$ axis by their rotation matrices:
$$
\begin{eqnarray}
\pmatrix{\cos\phi&-\sin\phi&0\\\sin\phi&\cos\phi&0\\0&0&1}\pmatrix{\cos\theta&0&\sin\theta\\0&1&0\\-\sin\theta&0&\cos\theta}\pmatrix{1\\0\\0}
&=&
\pmatrix{\cos\phi&-\sin\phi&0\\\sin\phi&\cos\phi&0\\0&0&1}\pmatrix{\cos\theta\\0\\-\sin\theta}
\\
&=&\pmatrix{\cos\phi\cos\theta\\\sin\phi\cos\theta\\-\sin\theta}
\;.
\end{eqnarray}
$$
You want this to be the unit vector along $(x,y,z)=(x_2,y_2,z_2)-(x_1,y_1,z_1)$, so you need
$$\theta=-\arcsin\frac zr$$
and
$$\phi=\arctan\frac yx\;,$$
where $r=\sqrt{x^2+y^2+z^2}$, and you'll want to use the atan2 function available in most programming environments to calculate the arctangent so you don't lose the sign information and don't have to divide by $0$ if $x=0$.
A: Define $u := \frac{1}{d} (x_2 - x_1, y_2 - y_1, z_2 - z_1)^T$, in which $d$ is the distance between your two points. This means, $u$ is the unit vector in the direction of the line segment. You are looking for a rotation that maps $e_x =  (1, 0, 0)$ to $u$.
The solution is not unique, as there are (infinitely) many rotations that achieve this, but you can single out the one that goes the most "direct" route - which is the one rotating about the axis perpendicular to both $u$ and $e_x$.
If you define $v := u \times e_x$ and $w := v \times u$ (using the cross product), the rotation matrix $R = (u, v, w)$ achieves exactly this (here, the vectors are the columns of $R$, which is a 3x3 matrix).
This matrix allows you to perform the desired rotation, and if all you need to do is rotate stuff, you should stick with it. However, if you really need to extract the rotation angles about the individual axes, it gets a bit ugly, bu see for example here for a way to do it.
A: Simply use the $y$-axis rotation to get it to the right height, and the $z$-axis rotation to swivel it into position. Specifically:  


*

*Start as in Mike K's answer: let $u = (u_x, u_y, u_z)$ be the unit vector parallel to $(x_2-x_1, y_2-y_1, z_2-z_1)$.

*To get $e = (1,0,0)$ to the right height, rotate it about the $y$-axis by angle $\theta = -\arcsin u_z$. Now the vector is $(\cos \theta, 0, \sin \theta) = (\cos \theta, 0, u_z)$.

*Rotate it around the $z$-axis by angle $\phi = \arcsin (u_y / \cos \theta)$. Now the vector is $(\cos \theta \cos \phi , \cos \theta \sin \phi, u_z) = (\cos \theta \cos \phi, u_y, u_z)$.  


Now, this is still a unit vector, so the $x$-coordinate must be correct up to sign. If it has the wrong sign, just replace $\phi$ by $180^{\circ} - \phi$.
