You don't prove this: this is a definition. The best you can ask for is a motivation for the definition. I'm guessing you're a freshman or sophomore from the book used, so you're likely finding vector and scalar products a bit bewildering and out of the blue. So here are a couple of motivations for the definition and some history: they are all related as I'll show. The cross product indeed has some interesting history.
Motivation 1: Velocity of Point in Spinning Body
The best way to motivate it is as the velocity vector $V$ of something a point in a rigid body whose position vector is $R$ when the rigid body spins about an axis through the origin with an angular velocity vector $\omega$. We define
$$V=\omega\times R$$
By convention, we give the angular velocity vector a magnitude equal to the spin rate in radians per unit time, and a direction pointing along the rotation axis, with a sense such that the rotation is anticlockwise. You can then easily see that $V$ is orthogonal to $R$ (because $\frac{\mathrm{d}}{\mathrm{d\,t}} \left<R,\,R\right> = 0$ i.e. $2\,\left<R,\,V\right> = 0$) and also orthogonal to $\omega$ (rotation leaves planes normal to $\omega$ invariant). Moreover, $|V|$ is given by $|\omega|$ times the orthogonal distance from the point to the rotation axis. That is, $|V| = |\omega||R|\sin\theta$ where $\theta$ is the angle between $R$ and $\omega$. There you have it.
More On Velocities
You may have to wait a little while to get the background to the following, but, as argued in my answer here and in Example 1.3 "Some Examples of Connected Lie Groups" on my website, the most general matrix describing a three dimensional rotation about an axis through the origin is $\exp(H)$, where $H=-H^T$ is a $3\times 3$, skew-symmetric matrix (meaning it switches sign when you "reflect it in the leading diagonal", i.e. rewrite its rows as columns). $\exp$ is the matrix exponential, which you define (exactly as for numbers) for any square matrices $H$:
$$\exp H = \mathrm{id} + H + H^2/2! + H^3/3!+\cdots$$
this always converges uniformly for finite matrices. In turn, some messy fiddling with this assertion shows that the most general rotation matrix, that of a rotation an angle $\theta$ about an axis with direction cosines $(h_x,\,h_y,\,h_z)$ is of the form:
$$\rho(\theta,\,h_x,\,h_y,\,h_z)=\exp(H(t))=\exp\left[\theta\,\left(\begin{array}{ccc}0&-h_z&h_y\\h_z&0&-h_x\\-h_y&h_x&0\end{array}\right)\right]$$
So now, if the body is spinning at a uniform angular speed $\omega$ so that $\theta = \omega \,t$, then a point with position vector $X=(x,\,y,\,z)^T$ at $t=0$ has velocity:
$$\left.\frac{\mathrm{d}}{\mathrm{d}\,t}\left(\rho(\omega \,t,\,h_x,\,h_y,\,h_z)\,X\right)\right|_{t=0} = \left.\omega\,\rho(\omega \,t,\,h_x,\,h_y,\,h_z)\,X\right|_{t=0} = H\,X = \left|\begin{array}{ccc}\hat{e}_x&\hat{e}_y&\hat{e}_z\\\omega\,h_x&\omega\,h_y&\omega\,h_z\\x&y&z\end{array}\right|$$
(you'll need to check the last step by working out $\omega\,\left(\begin{array}{ccc}0&-h_z&h_y\\h_z&0&-h_x\\-h_y&h_x&0\end{array}\right)\left(\begin{array}{c}x\\y\\z\end{array}\right)$ )
which gives you the definition used in Timbuc's Answer.
Motivation 2: Algebraic Definition
For the vector space $\mathbb{R}^3$ you can define the cross product as the unique, nontrivial binary operation $B:\mathbb{R}^3\times \mathbb{R}^3\to \mathbb{R}^3$ (modulo a scaling constant) with the following properties:
Billinearity: $B(x_1\,X_1+x_2\,X_2,\,y_1\,Y_1+y_2\,Y_2) = \\x_1\,y_1\,B(X_1,Y_1) + x_1\,y_2\,B(X_1,Y_2)+x_2\,y_1\,B(X_2,Y_1)+x_2\,y_2\,B(X_2,Y_2);\\\forall\,X_1,\,X_2,\,Y_1,\,Y_2\in\mathbb{R}^3,\;\forall x_1,\,x_2,\,y_1,\,y_2\in\mathbb{R}$
Skew Symmetry: $B(X,\,Y)=-B(Y,\,X);\;\forall\,X,\,Y\in\mathbb{R}^3$
Fulfils the Jacobi Identity $B(X,\,B(Y,\,Z)) + B(Z,\,B(X,\,Y)) + B(Y,\,B(Z,\,X))=0;\;\forall X,\,Y,\,Z\in\mathbb{R}^3$
AND
- Is invariant with respect to an even permutation of the orthonormal basis vectors $\hat{e}_x,\,\hat{e}_y,\,\hat{e}_z$.
You can then prove that the determinant definition used in Timbuc's answer has all these properties (existence). To prove that this uniquely defines the cross product up to a scaling constant, by billinearity we only have to work out $B(a,b)$ for pairs of basis vectors: the billinear map then follows. We first note that axioms 1. and 2. imply:
$$B(\hat{e}_x,\,\hat{e}_x)=B(\hat{e}_y ,\, \hat{e}_y)=B(\hat{e}_z ,\, \hat{e}_z)=0\tag{1}$$
Now we must have:
$$B(\hat{e}_x ,\, \hat{e}_y) = \alpha \hat{e}_x + \beta \hat{e}_y + \gamma \hat{e}_z\tag{2}$$
where $\alpha,\,\beta,\,\gamma$ are to be found. We cyclically permute the roles of the unit vectors, and by axiom 4 the relationship must be left unchanged:
$$B(\hat{e}_y ,\, \hat{e}_z) = \alpha \hat{e}_y + \beta \hat{e}_z + \gamma \hat{e}_x\tag{3}$$
and do the same again, then sum the three, cyclically permuted versions and apply the Jacobi identity to find that:
$$(\alpha+\beta+\gamma)(\alpha-\beta)=0\tag{4}$$
Now we take heed that $B(\hat{e}_x,\,\hat{e}_y)$, $B(\hat{e}_y,\,\hat{e}_z)$ and $B(\hat{e}_z,\,\hat{e}_x)$ must, by axiom 4, be three, mutually orthogonal vectors. Their sum must therefore be nonzero (unless $B$ is trivial), whence, from our three cyclically permuted versions of (2):
$$B(\hat{e}_x,\, \hat{e}_y)+B(\hat{e}_y,\,\hat{e}_z)+B(\hat{e}_z,\, \hat{e}_x)=(\alpha+\beta+\gamma)(\hat{e}_x+\hat{e}_y+\hat{e}_z)\neq0\tag{5}$$
so that now, from (4), $\alpha=\beta$ and so:
$$B(\hat{e}_x,\, \hat{e}_y) = \alpha(\hat{e}_x+\hat{e}_y) + \gamma\hat{e}_z\tag{6}$$
Now, by axiom (4) and axiom (1) (billinearity), this holds when we replace $\hat{e}_x,\, \hat{e}_y$ by any pair of orthogonal (wrt to the standard scalar product) $X$ and $Y$ and write the RHS in basis free notation: we write it in terms of the known cross product as defined in Timbuc's answer:
$$B(X,\, Y) = \alpha\,(X+Y) + \gamma X\times Y\tag{7}$$
in particular, $B(Y,\, X) = \alpha\,(Y+X) + \gamma Y\times X$, but, by axiom (2) (skew symmetry) we straight away conclude that:
$$0 = B(X,\,Y)+B(Y,\,X) = 2\,\alpha\,(X+Y) + \gamma\,(X\times Y + Y\times X)\Rightarrow \alpha (X+Y) = 0\tag{8}$$
and so $\alpha = 0$ and now (2) becomes
$$B(\hat{e}_x,\, \hat{e}_y) = \gamma \hat{e}_z\tag{9}$$
or, more generally, $B(X,\, Y) = \gamma\,X\times Y$. You now complete the proof that $X\cdot(X\times Y)=0$ as in Timbuc's answer, i.e the operation is needfully some scaled version of the cross product.
Motivation 3: Quaternions
The scalar and vector product together are working parts of a more intuitive whole: an invertible vector product. Suppose we have vectors $X, \,Y$, then the two products are the scalar $z=X\cdot Y$ and the vector $Z=X\times Y$. Now, suppose we know $z$, $Z$ and $X$: we can reconstruct from this information $Y$ as follows: we have the identity $X\times(X\times Y)=X\cdot Y X - |X|^2 Y$ so that
$$Y = \frac{1}{|X|^2}(z X - X\times Z)\tag{1}$$
i.e. we have retrieved $Y$, and we can do this as long as $X$ is nonzero so that $|X|^2\neq0$. The vector product $X\times Y$ is unchanged by the addition of any scalar multiple of $Y$ to $X$, i.e. $X\times Y = (X + \alpha\,Y)\times Y$. So, once again, we see why:
The scalar product is a scalar and is precisely the further information you need to "invert" the cross product
This futher information is $\alpha$ in the expression $X\times Y = (X + \alpha\,Y)\times Y$, which the vector product annihilates. So the scalar product's $X \cdot Y$ role is to fetch the component of $X$ in the direction of $Y$, i.e. the part annihilated by the vector product. If instead of 3 dimensional vectors, we think about four dimensional entities of the form $\chi = (x,\,X)$ where $x$ is a scalar and $X$ a three dimensional vector, we can define a new, generalised product on these entities using the scalar and vector product:
$$(x,\,X) \, (y,\,Y) \stackrel{def}{=} (x\,y - X\cdot Y,\,x\,Y + y\,X + X\times Y)$$
then, with a bit of fiddling, you can show that the inverse of the entity $(x,\,X)$ is indeed:
$$(x,\,X)^{-1} = \frac{1}{x^2+|X|^2}\,(x,\,-X)\tag{3}$$
and so the inverse exists and is unique as long as the "length" $x^2 + |X|^2$ of the entity $(x,\,X)$ is not nought. What you've now defined is in fact the skew field of quaternions and historically these were the first entities to be used for 3D spatial vector analysis before Oliver Heaviside and Josiah Gibbs "pruned" them back to the separate scalar and vector product. Sometimes calculations are easier with quaternions (I certainly find the angular momentum of a falling cat easier to think about with quaternions than vector products, as in my article here) or, more generally in Clifford Algebras, but it sounds as though it might be some time before you meet those. The case of "inverting the scalar and vector product" given in (1) is a special case of (2) and (3) when there are no scalar parts to the entities, i.e. when we deal with "pure vectors" (a.k.a. pure imaginary quaternions) of the form $(0,\,X)$ and $(0,\,Y)$.
The cross product was a long time in definition. James Clerk Maxwell wrote his electromagnetism equations in quaternion notation quite a long time before Gibbs and Heaviside "deprecated" quaternions. From a mathematician's standpoint, the quaternions are important as being a "near miss" to both of the following:
A field of characteristic 0 which has the same cardinality as $\mathbb{R}$ and which is algbraically closed (all polynomial equations with co-efficients from the field can be solved by entities within the field). $\mathbb{C}$ is the unique field with these three properties: the quaternions $\mathbb{H}$ fail to be a field because multiplication is non commutative
An example of $\mathbb{R}^N$ which can be kitted with a product that is also a valuation (i.e. $|x\,y| = |x||y|$) making it into a field. Again, $\mathbb{R}$ and $\mathbb{C}$ are the only examples; $\mathbb{H}$ fails to be a field because multiplication is non commutative.
So, intuitively, both the scalar and vector product form "working cogwheels" within the only possible product of vectors that makes something "maximally like" "normal numbers" $\mathbb{R}$ and $\mathbb{C}$; one cannot make it exactly like the "normal numbers", and it is the only way that one can make a skew field whose product is a valuation as in $\mathbb{R}$ and $\mathbb{C}$.
Links Between the Motivations
There are indeed strong links between all of these motiviations (aside from that you can brute force prove them to be the same). Rotations form a group, an example of a Lie group wherein the group product is continuous. Tangents to paths through the identity in such groups, such as I calculated when I calculated $\left.\frac{\mathrm{d}}{\mathrm{d}\,t}\left(\rho(\omega \,t,\,h_x,\,h_y,\,h_z)\,X\right)\right|_{t=0}$, form what is called the Lie algebra of the group, and it has a product that must always fulfil the billinearity, skew-symmetry and Jacobi identity - so these axioms are a necessary condition for the product to be a space of "velocities" corresponding to a group of continuous transformations. A messy and fiddly thing called Ado's theorem shows that the condition is also sufficient. So, whilst the rotation group is not the only three dimensional Lie group (thus not the only thing whose algebra of "velocities" fulfills the billinearity, skew-symmetry and Jacobi axioms), it is the only one that "ignores" the basis and treats $\hat{e}_x,\,\hat{e}_y,\,\hat{e}_z$ on an equal footing.
Best Answer
Here's an informal proof that if $u$ and $v$ are orthogonal unit vectors, then $w = u \times v$ follows the right hand rule:
Observe that it's true that for $u = i$ and $v = j$, it works. You could imagine placing a plaster cast of a right-hand with the index finger along $i$, the pinky extended along $j$, and the thumb pointing along $k$.
Observe that for any rotation $R$ and any vectors $p$ and $q$, $Rp \times Rq$ is $R(p \times q)$. [That's just a computation with a lot of algebra.]
Observe that you can always find a rotation $R$ that sends $i$ to $u$. It'll send $j$ to some vector $v'$ perpendicular to $u$. Now rotate about the vector $u$ until $v'$ aligns with $v$. Call that $S$. The operation "rotate by $R$ and then $S$" can be applied not only to $i$ and $j$ but also to the entire plaster hand. By item 2, the vector $z$ will be rotated, by this same pair of rotations, to the direction of the thumb.
Here's a slightly more formal proof, again for the case where $u$ and $v$ are unit vectors, perpendicular to each other (which I'll call a 2-frame in 3-space).
The entries of the cross product $w = u \times v$ are polynomials in the entries of $u$ and $v$, so thinking of $w$ as a function of $u$ and $v$, it's a continuous function.
Of the two unit vectors perpendicular to both $u$ and $v$, one satisfies the right hand rule and one does not. The distance between these two is exactly $2$ (because they're negatives of one another).
The right-hand-rule vector, $R(u, v)$, for any pair of vectors $u$ and $v$, varies continuously as a function of $u$ and $v$: if you rotate $u$ a little bit about $v$, the right-hand vector will also rotate a little bit. More formally, if $u'$ and $v'$ are distance less than 0.1 from $u$ and $v$ respectively, then $R(u', v')$ and $R(u, v)$ differ by less than $1$ (i.e., the distance between them is a vector of length less than one).
For $u = i, v = j$, the right-hand-rule vector $R(u, v) = k$.
So: for $u$ near $i$ and $v$ near $j$, the right-hand rule vector must be near $k$. Since $R(u,v)$ must be either $u \times v$ or $-u \times v$, and it's near $k$, it must be $u \times v$.
The set of $(u,v)$ pairs for which $R(u,v) = u \times v$ is an open set in the space of all 2-frames in 3-space, by an extension of the argument in part 4. It's also a closed set, so it must be a connected component of the space of frames. Since any two frames can be connected by a path of frames, the whole space of 2-frames is path-connected, hence connected, so the connected component must be the whole space of 2-frames. In short: the set of frames $(u, v)$ where $R(u, v) = u \times v$ is all frames.