There have been two good answers as to how you might prove it, depending on the logical system. But it might also help to think about exactly why it must be true.
Suppose you have a mathematical function $f : A\times B \rightarrow C$. That is, it takes an element of type $A$ and an element of type $B$, then it returns an element of type $C$.
Now consider a function $f' : A \rightarrow (B \rightarrow C)$. This is a function that takes an element of type $A$ and returns a function. This function, in turn, takes an element of type $B$ and returns an element of type $C$.
Can you see that these are, in a sense, equivalent? You might call the first function by passing a pair $f(a,b)$ and the second one by passing an element, then passing an element to the function returned, like $(f'(a))(b)$. Either way, you get an element of $C$ by passing in an element of $A$ and an element of $B$.
So the types $A \times B \rightarrow C$ and $A \rightarrow (B \rightarrow C)$ are isomorphic. For every function of one type, there is a function of the other type which does the same thing. Using set exponent notation makes this even more obvious: it's saying that $C^{A \times B}$ is isomorphic to $(C^B)^A$.
It may not be obvious what this has to do with logic, but actually the connection is extremely deep and completely rigorous. If you're interested, look up the Curry-Howard correspondence, or Curry-Howard isomorphism.