Cartesian Space
In Cartesian space, three variables (XYZ) are used to describe the position of a point in space, typically an atomic nucleus or a basis function. To describe the locations of two atomic nuclei, a total of 6 variables must be written down and kept track of. The general ruling is that for Cartesian space, 3N variables must be accounted for (where N is the number of points in space you wish to index).
Internal Coordinates
Z-matrices use a different approach. When dealing with Z-matrices, we keep track of the relative positions of points in space. Cartesian space is 'absolute' so to speak. A point located at (0,0,1) is an absolute location for a coordinate space that extends to infinity. However, consider a two atom system. The translation of the molecule through space (assuming a vacuum) will have no affect on the properties of the molecule. An H2 molecule centered around the origin (0,0,0) is no different from the same H2 molecule being centered around (1,1,1). However, say we increase the distance between the hydrogen atoms. We now have altered the molecule in such a way that the properties of that molecule has changed. What did we change? We simply changed the bond length, one variable. We increased the distance between the two atoms by some length R. With Z-matrices, we keep tabs on internal coordinates: bond length (R), bond angle (A), and torsional/dihedral angle (T/D). Using internal coordinates reduces our 3N requirement set by the Cartesian space down to a 3N-6 requirement (for non-linear molecules). For linear molecules we keep tabs on 3N-5 coordinates. When performing complex computations, the less you have to keep track of, the less expensive the computation.
Symmetry
Consider the following molecule, H2O. We know from experience that this molecule has C2V symmetry. The OH bond lengths should be equivalent. When using some sort of optimizing routine, you may want to specify symmetry in your system. With a Z-matrix, the process is very straightforward. You would construct your Z-matrix to define the OH(1) bond as being equivalent to the OH(2) bond. Whatever program you use should automatically recognize the constraint and will optimize your molecule accordingly giving you an answer based off a structure that is constrained to C2v symmetry. With Cartesian space this is not guaranteed. Rounding errors can cause your program to break symmetry, or your program may not be very good at guessing the point group of your molecule based on the Cartesian coordinates alone.
Picking the Right One
As a preface, programs like Gaussian convert your Cartesian coordinate space (or your pre-defined Z-matrix) into redundant internal coordinates before proceeding with an optimization routine unless you specify it to stick with Cartesians or your Z-matrix. I warn you that specifying your program to optimize using Cartesian coordinates makes your calculation much more expensive. I find that I will explicitly specify 'Z-matrix' when I know I'm dealing with high symmetry and when I know my Z-matrix is perfect.
You will want to use Z-matrices on systems that are rather small. If dealing with systems with high symmetry, Z-matrices are almost essential. They can be rather tricky to implement and you will likely spend some time figuring out the proper form of your Z-matrix through trial-and-error. If you wish to scan a particular coordinate, Z-matrices are also very helpful as you can tell a program to scan across a bond length, angle or torsion with ease (as long as you've properly defined that coordinate in your Z-matrix).
I use Cartesian coordinates for large systems, systems with very little or no symmetry, or when I'm in a hurry.