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
You are correct that there are two different unit vectors that are perpendicular to a given plane. As such, in order to have a well-defined cross product, we must make a choice, by convention, of which of these two vectors we will use. The only requirement on this choice is that it must be consistent everywhere we use it; we aren't allowed to switch from one choice to the other arbitrarily. There are two possible choices for the above product; the conventional choice is $\hat{i}\times\hat{k}=-\hat{j}$, which we call the right-hand rule because the direction can be easily calculated using the right hand. This choice also fixes all other unit vector products in such a way that $\hat{i}\times\hat{j}=\hat{k}$, $\hat{j}\times\hat{k}=\hat{i}$, and $\hat{k}\times\hat{i}=\hat{j}$ (basically, any cyclic permutation of the unit vectors in "alphabetical order" gives a positive result). Since the cross product is antisymmetric (not commutative!), swapping the two unit vectors in any of the above examples gives you the negative of the original result.
The unconventional choice is $\hat{i}\times\hat{k}=\hat{j}$, which is sometimes called the left-hand rule, for the same reason. This choice gives you opposite signs on all of the unit vector products above (i.e. the "alphabetical order" choices are negative, and swapping the two inputs in any one of them gives you the positive result). We generally don't ever use this one, but physics would be no different if we did, as long as our choice for the definition of the cross product is consistent.