There is a wealth of information in the tutorials accessed via Help > Wolfram Documentation. For your purposes the one below is likely to be best. As resources go, it is certainly an authority for the topic at hand.
tutorial/ComplexPolynomialSystems
Also bear in mind that Solve might perform certain "preprocessing" such as separating out linear subsystems, factoring to get disjunctions, and the like. That said, here are some specific answers.
(1) If we are solving over complexes, then a Groebner basis will be computed. This is independent of whether the system is over-, under-, or exactly-determined. Indeed, one will typically not know until such a basis has been computed.
(2) In theory, always. In practice, it is subject to limitations of computer memory, how long you might be filling to wait, and the like.
(2b) If restricting to reals, Solve might instead use methods from Real Algebraic Geometry such as Cylindrical Algebraic Geometry (CAD). This will almost certainly be the case when the system is under-determined over the complexes, since one cannot just find all finitely many solutions and discard complex-valued ones in that scenario.
(3) Solve might use validated approximation methods inside CAD, I'm not sure. It does not use Newton's method or similar. NSolve does not use them either except perhaps for root polishing (getting more correct digits from a root that was numerically approximated). If I remember correctly, this might be done in situations where the code indicates the possibility of multiplicity in the solutions.
