To see why the graph displays a function, ignoring the origin for the moment, note that the "vertical line test" you may be thinking of is inappropriate for polar functions. Each value of $\theta$ specifies a line through the origin, and it is this line which should only pass through one point on the graph. However this test is still inappropriate, because there are multiple values of $\theta$ which specify the same line through the origin (specifically, $\theta+\pi n$ for every integer $n$), so it is possible for a graph of a polar function to have many values passing through the same line through the origin.
In this particular case, every nonvertical line through the origin passes through two points of the graph: one on the origin, and the other elsewhere. It is the other point that the equation $r = \cos \theta$ specifies. On the vertical line, $\theta = \pi/2+\pi n$, we have $\cos\theta=0$, so this gives the origin.
As for why this gives a circle, the other answers have given algebraic proofs for this. I'm partial to the one Thomas and Luis gave, which multiplies by $r$ first, to give $r^2 = r\cos \theta$, myself. ;)