Hi, is shading performed before or after for instance a hidden surface removal algorithm such as z-buffering?
Both, and it depends. 
I should probably elaborate.
AFAIK, In older (fixed function) hardware the shading was done before the z-test, no exceptions. On newer hardware (ones that have fragment shaders) it depends on what the fragment shader program does. Provided the fragment shader program doesn’t alter the z value of the fragment the driver/graphics card can optimize this by doing the z test first. If the fragment is obscured it is simply discarded and the resources that would have been required to shade that fragment aren’t required. If the fragment program alters the z value then the z-test has to be done after the fragment program is finished.
Hehe, it reminds me about an argument with a teacher who thought that the z test was done before shading/texturing.
In fact having a pre-lighting z-test on the hardware with fixed function is indeed not useful, it would only create bubbles in the pipeline, and have almost no performance gain. It can be useful howerer, with heavy multitexture or anisotropic+trilinear filtering.
With complex fragment shaders of course it can be much more useful.
How does a spearate z-pass create a pipeline bubble?
@harsman: apparently I did not myself very clear. I was talking about the order of the operations in the pipeline. Not about separate rendering passes (I edited my post to improve it a bit).
To the original poster, here are some diagrams explaining fairly well the situation :
http://www.ap.dell.com/images/global/topics/vectors/2002-graphics-001.gif
http://www.gris.uni-tuebingen.de/~meissner/publications/presentations/eghww98occ/im g024.gif
http://www.tommti-systems.com/main-Dateien/reviews/asusgeforce3deluxe/zcull.jpg
You can see the visibility test is almost the last operation in the general case. The hyper-Z (hz) ati optimisation was recently added to enhance perfs for the cases mentionned above (big FP with no z modification and fixed-path with heavy texture access).