What does it mean if divergence of a vector field is zero? I learnt the identity that if $F$ is $C^2$ then div(curl$F$)=$0$. 
Now if I have a vector field $G$, which happens to be that div$G$ = $0$, does this mean that $G$ is the curl of some vector field $F$?
How would I find this if so?
 A: We can prove that  
$E=$curl$(F) \Rightarrow$ div$(E)=0$ 
simply using the definitions in cartesian coordinates and  the properties of partial derivatives.  But this result is a form of a more general theorem that is formulated in term of exterior derivatives and says that:

the exterior derivative of an exterior derivative is always null.

In this case $E$ is the exterior derivative of $F$ and div$(E)$ is the exterior derivative of $E$.
Another way to express this general result is to say that $E$ corresponds to an exact differential form just because it is the exterior derivative of a $1-$form corresponding to $F$ and the derivative of an exact form is null.
The question if the inverse is true, i.e. if a form whose exterior derivative is null (we say that it is closed) is necessarly exact, is solved by the Poincaré Lemma that says that:

all closed differential $k-$forms on a contractable domain are exact.

This is a very deep result that has to do with the topological fact that  the boundary of a boundary is zero (see this proof of div$($curl$(F))=0$) and require a definition of contractable space and, more, opens the doors of the de Raham cohomology theory (as you can see here if you want to know more about the argument).
Your last question about how we can find the vector potential of a field with null divergence, can be reduced to an integration problem as you can see here. 
