Why does the Cross Product have to be perpendicular to the two vectors? I understand that the cross product of two vectors equals the area of the parallelogram. But I don't understand why multiplying the two vectors gets you a vector perpendicular to the two vectors. 
 A: There is deep math here, but I get the sense that you're just learning about cross product.
The idea of the cross product is to multiply two vectors and get another vector, but how do you pick a third direction from two arbitrary directions?  Well, it turns out that in three dimensions, linear algebra tells us that if your first two vectors are not parallel, then there is a unique third direction that is "left over" from those two directions -- namely, the direction perpendicular to both of them.  
It turns out that this is the ONLY way to multiply two vectors and get a third vector in three dimensions (and too have the multiplication function satisfy the "normal" things we expect of multiplication)
A: Because $a\cdot(a\times b)=\sum_{ijk}\epsilon_{ijk}a_ia_jb_k$ is $0$, due to the contraction of the $i\leftrightarrow j$-antisymmetric Levi-Civita symbol with the $i\leftrightarrow j$-symmetric $a_ia_j$. Similarly, $b\cdot(a \times b)=-b\cdot(b\times a)=0$.
A: Another way of looking at it is that you want the cross product of two vectors not to be in the same direction as them. Since the two vectors are not parallel, they form the basis of an entire plane, and what you want is consequently that their cross product should not be in that plane: that is, that it should be normal to it. 
In three dimensions, that gives you only one direction to go, and two ways you can go along that direction. Deciding which of those ways to use is purely a matter of convention, like deciding which square root of -1 is i and which is -i.
In four dimensions the whole thing would be more difficult because the normal to the plane of the original two vectors is itself a plane, not a line. 
A: The vector product is unique to 3 dimensions.
From 2 vectors, $\vec a=(a_1,a_2,a_3)$ and $\vec b=(b_1,b_2,b_3)$, one can form not only the familiar scalar product $\vec a . \vec b=a_1b_1+a_2b_2+a_3b_3$, which is a number, but also the Cartesian product $\vec a \otimes \vec b = \left( \matrix{a_1b_1,a_1b_2,a_1b_3\\a_2b_1,a_2b_2,a_2b_3\\a_3b_1,a_3b_2,a_3b_3}\right)$, which is a square matrix.
Likewise $\vec b \otimes \vec a = \left( \matrix{b_1a_1,b_1a_2,b_1a_3\\b_2a_1,b_2a_2,b_2a_3\\b_3a_1,b_3a_2,b_3a_3}\right)$.
The two are different and if you subtract one from the other you get an antisymmetric matrix
$\vec a \otimes \vec b - \vec b \otimes \vec a = \left( \matrix{0,a_1b_2-b_1a_2,a_1b_3-b_1a_3\\a_2b_1-b_2a_1,0,a_2b_3-b_2a_3\\a_1b_3-b_3a_1,a_3b_2-b_3a_2,0}\right)$.
An $N \times N$ antisymmetric matrix like this has ${1 \over 2} (N^2-N)$ independent values, and it just happens that for $N=3$ this is 3. (For $N=2$ it is 1, and for $N=4$ it is 6. ) We can match these 3 values onto the 3 components of a new vector, and this is done using the antisymmetric $\epsilon_{ijk}$, as noted in @J.G.'s answer above: the 1-2 element in the matrix gives the 3rd element in the vector, and so on cyclically. This gives $\vec a \times \vec b =(a_2b_3-a_3b_2,a_3b_1-a_1b_3,a_1b_2-a_2b_1)$. If you take the scalar product with $\vec a$, or $\vec b$, this gives zero, as can be seen from the properties of the Levi-Civita symbol or just by multiplying out.
