On the Euclidean plane, no circle intersects itself. In contrast, on the cylinder, a sufficiently big circle intersects itself.
Since a circle consists of points at distance $r$ on all geodesics through the origin, the possibility of the existence of self-intersecting circles is equivalent to the existence of different geodesics intersecting each other in more than 1 point.
On the Euclidean plane, every pair of different geodesics meet at most one point.
On the cylinder, different geodesics can meet more than one. The Euclidean plane and the cylinder are both curvature-free. The difference between the Euclidean plane and the cylinder is that the cylinder is not simply connected.
However, multiple connectedness isn't necessary for the existence of multiply meeting geodesics. On the sphere, every two different geodesics meet twice. The sphere is simply connected just as the Euclidean plane, but unlike the Euclidean plane, it has a nonvanishing curvature.
Both the nonvanishing curvature and the multiple connectedness can allow different geodesics to meet each other more than once, and neither is necessary nor enough for this. So what is common in such spaces?
Here is my interpretation of the question:
Let $M$ be a 2-dimensional connected Riemannian manifold, where I suppress the notation for the Riemannian metric. To simplify things, I will assume that $M$ is complete, so at least exponential maps are everywhere defined and, hence, "circles" in your question do look like circles rather than arcs or collections of arcs.
The "circles" in your question are the restrictions of the exponential map $\exp_p$ to round circles $C$ centered at zero in the tangent space $T_pM$. One says that a circle is "self-intersecting" if this restriction is non-injective. Thus, effectively, you are asking about the causes of non-injectivity of the exponential map $\exp_p$ (for various points $p$).
There are two sources of non-injectivity (the dimension 2 assumption is irrelevant here):
a. $\exp_p$ may fail to be locally injective. For instance, $M$ may have conjugate points. The most common way to eliminate conjugate points (and force local injectivity) is to assume that $M$ has curvature $\le 0$.
b. $\exp_p$ might be locally injective but not globally injective. One common source of this global failure is that $M$ can fail to be simply-connected (this is what happens in the cylinder examples that you mentioned). Let $\pi: \tilde{M}\to M$ denote the universal covering map, where I equip $\tilde{M}$ with the pull-back Riemannian. metric.
In this situation, the exponential map $\exp_p$ will factor as the composition $$ T_pM \stackrel{d_q\pi^{-1}}{\longrightarrow} T_q\tilde{M}\stackrel{\exp_q}{\longrightarrow} \tilde{M} \stackrel{\pi}{\longrightarrow} M $$ where $\pi(q)=p$. Since the last map is not injective, so is $\exp_p$.
What do failures of local and global injectivity have in common? Not much, besides non-injectivity.
Lastly, the most common way to guarantee injectivity (actually, diffeomorphism) of exponential maps is to assume that $M$ is a Hadamard manifold, i.e. is complete, simply-connected and of sectional curvature $\le 0$. This is the content of the Cartan-Hadamard theorem.