Let's assume you define the dot product as [itex]A\cdot B = A_xB_x+A_yB_y+A_zB_z[/itex]. You can easily show that rotations don't affect the dot product. If you have two vectors A and B and rotate the system so they are now A' and B', you'll get the same result for the dot product using either pair, i.e. [itex]A\cdot B=A'\cdot B'[/itex]. So you can always perform a rotation so that A points along the x-axis, so that A = |A|(1,0,0). The dot product will therefore equal [itex]A\cdot B = |A|B_{x}[/itex]. Now [itex]B_{x}[/itex] is just the projection of B onto the x-axis, which, using basic trig, is [itex]B_{x} = |B|\cos \theta[/itex], where [itex]\theta[/itex] is the angle B makes with the x-axis, which is also the angle between A and B. So you get [itex]A\cdot B = |A||B|\cos\theta[/itex].
The dot product is a special case of what's called an inner product. The definition above is the inner product for plain old three-dimensional Euclidean space, but other spaces are characterized by having a different inner product. If you have two vectors A and B in such a space, you can use
[tex]\cos\theta=\frac{\langle A,B\rangle}{\sqrt{\langle A,A\rangle}\sqrt{\langle B,B\rangle}}[/tex]
where [itex]\langle A,B\rangle[/itex] is the inner product of A and B, to define angles in this space. In this case, the cosine is there by definition.