Why does cross product give a vector which is perpendicular to a plane

The determinant formula isn't so mysterious. Consider the cross product $\mathbf{v} = \langle a,b,c \rangle \times \langle d,e,f \rangle$ as the formal determinant

$$ \det \left(\begin{array}{ccc} \mathbf{i} & \mathbf{j} & \mathbf{k}\\ a & b & c \\ d & e & f \end{array} \right) $$

where $\mathbf{i}, \mathbf{j}, \mathbf{k}$ are the standard basis vectors. If instead one considers $\mathbf{i}, \mathbf{j}, \mathbf{k}$ as indeterminates and substitutes $x, y, z$ for them, this determinant computes the dot product $\mathbf{v} \cdot \langle x, y, z \rangle$. But letting $\langle x, y, z \rangle$ be $\langle a, b, c \rangle$ or $\langle d, e, f \rangle$ gives a zero determinant, so $\mathbf{v}$ is perpendicular to the latter two vectors, hence to the plane they span, as Omnomnomnom says.

According to Prof. Josiah Willard Gibbs, one of the founders of Vector Analysis, the cross (or skew) product is defined as follows in his 1881 pamphlet Vector Analysis - Arranged for the use of Students in Physics

Definition: The skew product of the vector A into the vector B is the vector quantity C whose direction is the normal upon that side of the plane of A and B on which rotation from A to B through an angle of less than one hundred and eighty degrees appears positive or counter- clockwise ; and whose magnitude is obtained by multiplying the product of the magnitudes of A and B by the sine of the angle from A to B.

This definition, coming from the horse's mouth, as it were, is a geometric definition. Why then, do we in the 21st c. insist on defining it in terms of determinants. The determinant "definition" is a direct consequence of the geometric definition and the distributivity of cross products $$\vec{\mathbf{w}}\times(\vec{\mathbf{u}}+ \vec{\mathbf{v}}) = \vec{\mathbf{w}}\times\vec{\mathbf{u}}+\vec{\mathbf{w}}\times\vec{\mathbf{v}}$$ $$(\vec{\mathbf{u}}+ \vec{\mathbf{v}})\times\vec{\mathbf{w}} = \vec{\mathbf{u}}\times\vec{\mathbf{w}}+\vec{\mathbf{v}}\times\vec{\mathbf{w}}$$ now try to expand $$(a_1\vec{\mathbf{i}}+a_2\vec{\mathbf{j}}+a_3\vec{\mathbf{k}})\times(b_1\vec{\mathbf{i}}+b_2\vec{\mathbf{j}}+b_3\vec{\mathbf{k}})$$ to see that cross products, in fact, distribute over addition, see a geometric proof on page 9 of http://www.math.oregonstate.edu/bridge/papers/dot+cross.pdf

See what happens when you try to take $(a\times b)\cdot a$ or $(a\times b)\cdot b$ (you should get $0$). If a vector is perpendicular to a basis of a plane, then it is perpendicular to that entire plane. So, the cross product of two (linearly independent) vectors, since it is orthogonal to each, is orthogonal to the plane which they span.

Also, while you're trying to develop an intuition for cross products, I highly recommend this video

https://www.khanacademy.org/math/linear-algebra/vectors_and_spaces/dot_cross_products/v/proof--relationship-between-cross-product-and-sin-of-angle

and, while we're there, might be worth knowing how the angle formula for dot products comes from the law of cosines

https://www.khanacademy.org/math/linear-algebra/vectors_and_spaces/dot_cross_products/v/defining-the-angle-between-vectors