There are two other interpretation of the Pauli matrices that you might find helpful, although only after you understand JoshPhysics's excellent physical description. The following can be taken more as "funky trivia" (at least I find them interesting) about the Pauli matrices rather than a physical interpretation.
1. As a Basis for $\mathfrak{su}(2)$
The first interpretation is variously seen as (i) they are unit quaternions, modulo a sign change and reordering of the mathematician's definition of these beasts, (ii) as a basis for the Lie algebra $\mathfrak{su}(2)$ of $SU(2)$ when we use the matrix exponential to recover the group $SU(2) = \exp(\mathfrak{su}(2))$ through (iii) a three dimensional generalisation of De Moivre's theorem.
A general, traceless, $2\times2$ skew Hermitian matrix $H$ can be uniquely decomposed as:
$$H = \alpha_x \sigma_x + \alpha_y \sigma_y + \alpha_z \sigma_z\tag{1}$$
with $\alpha_x,\,\alpha_y,\,\alpha_z\in \mathbb{R}$. This matrix fulfils the characteristic equation $H^2 = -\frac{\theta^2}{4}\,\mathrm{id}$, where $\mathrm{id}$ is the $2\times2$ identity and $\frac{\theta}{2} = \sqrt{\alpha_x^2+\alpha_y^2+\alpha_z^2}$. So, if we deploy the universally convergent matrix exponential Taylor series, and then reduce all powers of $H$ higher than the linear term with the characteristic equation, we get:
$$\exp\left(H\right) = \cos\left(\frac{\theta}{2}\right)\mathrm{id} + \hat{H}\sin\left(\frac{\theta}{2}\right)\tag{2}$$
which is seen to be a generalisation of De Moivre's formula for the "pure imaginary" unit
$$\hat{H} = \frac{\alpha_x \sigma_x + \alpha_y \sigma_y + \alpha_z \sigma_z}{\sqrt{\alpha_x^2+\alpha_y^2+\alpha_z^2}}\tag{3}$$
and all members of $SU(2)$ can be realised by an exponential such as in (2) (but be aware that the exponential of a Lie algebra, although the whole of $SU(2)$ in this case, is not always the whole Lie group unless the latter is (i) connected and (ii) compact). Thus every member of $SU(2)$ can be decomposed as a "unit length superpositon of the Pauli matrices and the identity matrix.
The reason for the factor 2 in the definition $\theta/2$ is so far mysterious: witness that for the purposes of the above, we might just as easily have replaced $\theta/2$ by $\theta$. The reason is related to the relationship between the Pauli matrices and the Celestial sphere, which I discuss later on. Quaternions represent rotations through a spinor map (BUT, as Joshphysics advises, don't be distracted too much by this word); if a vector in 3-space is represented by a purely imaginary quaternion of the form $x\,\sigma_x+y\,\sigma_y+z\,\sigma_z$, then its image under a rotation of angle $\theta$ about an axis with direction cosines $\gamma_x,\,\gamma_y,\,\gamma_z$ is given by:
$$x\,\sigma_x+y\,\sigma_y+z\,\sigma_z \mapsto U\,(x\,\sigma_x+y\,\sigma_y+z\,\sigma_z)\,U^\dagger;\quad U=\exp\left(\frac{\theta}{2}(\gamma_x\,\sigma_x+\gamma_y\,\sigma_y+\gamma_z\,\sigma_z)\right) \tag{4}$$
This spinor map is an example of the group $SU(2)$ acting on its own Lie algebra through the adjoint representation. It can be intuitively understood in terms of a triangle rule to work out the compositions of two rotations, as sketched in my diagram below. The arcs on the unit sphere represent a rotation through an angle twice that given by the angle subtended by the arc at the origin.
I explain this in detail in Example 1.4 "$2\times2$ Unitary Group $SU(2)$" on my web page "Some Examples of Connected Lie Groups" here.
There is also my interactive Mathematica demonstration "The $SU(2)$ Spinor Map: Rotation Composition by Graphical Quaternion Triangles" on the Wolfram Demonstrations site.
2. The Celestial Sphere
By expanding the 3 dimensional linear space of superpositions of Pauli matrices (which is the same as the linear space of traceless $2\times2$ skew-Hermitian matrices) to the 4 dimensional space spanned by the Pauli matrices and the identity matrices, then any transformation from the group $SL(2,\,\mathbb{C})$ acts on vectors of the form $t\,\mathrm{id}+x\,\sigma_x + y\, \sigma_y + z\,\sigma_z$ by the same spinor map as in (4). If we restrict ourselves to projective rays in this space, the group $SL(2,\,\mathbb{C})$, isomorphic to the Moebius group of Möbius transformations acts on this space of rays in exactly the same way as Möbius (fractional linear) transformations act on the Riemann sphere. $SL(2,\,\mathbb{C})$ is a double cover of the Lorentz group, and you can calculate how the view of a spacefarer changes as they undergo Lorentz transformations. See the section "Lorentz Transformations" on the Wikipedia "Möbius Transformation" page for further details.