It's sort of a combination, but most happens on the server.
What happens is this:
1) User clicks. Client sends a "shot" message, along with positional data.
2) Server processes the shot data. It determines, from last known positional data, if that shot hit.
3) If the shot hit, the server determines amount of damage and updates all players.
So as to your question, the basic (English) exchange looks like this:
Client: Hey server, I fired a shot! I was at X position, and I fired in Y direction!
Server: OK everyone, Client # fired a shot.
*Server looks at where Client fired, and if the client hit...
Server: Client # hit client # for Z damage.
From here, the server determines if it was a kill. If so, it sends the appropriate messages.
(However, the client also does this as well, but the server is the one that has authority. That's why you will occasionally see the hit crosshair but not get the kill when you and someone else shoot at the same time - their data got to the server first, so they got the kill from the server, but your client showed the crosshair because it believed you got the frag.)
Lag becomes an issue when positions don't get updated. For instance, someone with a 1000 ms lag (1 second) could get shot even if they were in a different place, since the server uses the last known position. So if you have high ping, people could be shooting at where you were a second ago and still hit you since you have not updated your position to the server and it still thinks you were where you were a second ago. Make sense?