How are these two ways of thinking about the cross product related?

To expand on Victork Protsak's comment, if $V$ is an $n$-dimensional real vector space with inner-product, the inner-product gives an isomorphism $V\to V^*$ and hence $V\otimes V \to \mathrm{End}(V)$. Under this isomorphism, $\Lambda^2(V)$ is identified with skew-adjoint endomorphisms of $V$, which is precisely the Lie algebra $\mathfrak{so}(V)$.

In the case $\dim V =3,$ the Hodge star gives an isomorphism $\Lambda^2(V) \to V$ and so in total we see that $V$ is canonically isomorphic to $\mathfrak{so}(V)$. A more direct way to see this isomorphism is to send the vector $v \in V$ to the generator of the right-handed rotation about the axis in the direction of $v$ with speed $|v|$.

The use of the phrase "right-handed" makes it clear that in order to identify $V$ and $\mathfrak{so}(V)$ we have used an orientation on $V$; indeed, you need that for the Hodge star. What is interesting is that if you reverse the orientation on $V$, the map to $\mathfrak{so}(V)$ changes sign. This means that what ever orientation you chose on $V$, the push-forward to $\mathfrak{so}(V)$ is the same. Conclusion: $\mathfrak{so}(3)$ is naturally oriented. This is analogous to the natural orientation on $\mathbb{C}$. A more prosaic way to describe the orientation is to pick two independent elements $x,y \in \mathfrak{so}(3)$ and then use $[x,y]$ to complete them to an oriented basis. (Of course, you then need to check that this doesn't depend on your choice of $x,y$.)

Let $\varepsilon( )$ be the volume form in $\mathbb R^3$. For given vectors ${\bf p}$ and ${\bf q}$ the function $f:{\bf x}\mapsto\varepsilon({\bf p},{\bf q},{\bf x})$ is a linear functional and so is represented by a vector ${\bf r}\in\mathbb R^3$, i.e., one has $f({\bf x})=\langle{\bf r},{\bf x}\rangle$. This vector ${\bf r}$ depends in a skew bilinear way from ${\bf p}$ and ${\bf q}$ and is called the $vector\ product$ of ${\bf p}$ and ${\bf q}$.

Geometric (Clifford) algebra provides yet another way to understand the cross product. If a vector represents a 1D subspace containing the origin, the wedge (outer) product is a bilinear form on 2 vectors ($a \wedge b$) that represents the subspace containing both vectors. The vector has basis $e_1, e_2, ..., e_n$ ($n$ elements), so the wedge product has basis $e_1\wedge e_2, e_1\wedge e_3, \ldots, e_{n-1}\wedge e_n$ ($\binom{n}{2}$ elements). The cross product is a way to represent this subspace (using its dual, the normal vector). This works only for 3D, where the basis sizes match, using $e_1 e_2 \to e_3,\, e_2 e_3 \to e_1,\, e_3 e_1 \to e_2$.