I have not implemented a network strategy myself, but I have already read some related texts and thought about network solutions for my game engine project. So maybe I can give you a small overview.
I recall reading that in Team Fortress 2, the computer tracks the trajectory of every projectile including every bullet, rocket. It seems like that would generate a tsunami of messages, ...
It isn't really necessary to update everything every frame of your game loop. Many things can be omitted. For example: For a bullet, all you need to know to describe it's movement is the time and direction it was fired and some additional data that influences the trajectory like initial movement speed and external forces (gravity, drag, etc.). With this information, every computer can calculate the current position on its own. They might come to slightly different results due to different time steps, floating-point errors or hardware, but as long as they do not have relevant impacts on the worlds state (hitting a player/destroyable object, change environment states, etc.) it doesn't really matter if the point of impact varies by 2cm between 2 computers. So you just need to sync those projectiles that might affect the game world's global state and only in the time range where this is going to happen.
It is not really that much different for player movements. The player just hits a button at a certain time to trigger an action. It is not like the player is actually controlling every limp himself. His computer calculates the resulting animation state and movements which can be recalculated on every other computer that has the same information. So you just need to know at which time another player performs which action and you computer can more or less predict his movement and animations in the next frames.
Another optimization is to just let the server send data to a player that is actually relevant for him. Something a player can't see and that can't affect him doesn't need to be synchronized. So the server can decide based on the player's location and viewing direction what is relevant for him.
I've noticed gaps in the magician's curtain when severe lag occurs. Sometimes other players "teleport"; they're not where I think they are. Other times, I can peer around a corner and be killed when there's no-one there; except shortly after I see the other victorious player.
Due to the network latency, all the updates you get from the server arrive usually "too late". You get the information about what another player did a certain amount of milliseconds ago. However, your computer can predict what he is probably doing "now" from that information. There are some techniques to avoid jumps in movements and animations due to getting updates too late.
For example, if you get the information that a player changed his movement 100ms ago and your computer mispredicted it, instead of instantaneously moving him to the correct position you can just speed up his movement into the correct direction so that his position on your computer will be synchronized again a few frames later. Usually, you won't notice the slightly increased speed. Of course, if the latency gets too high (lag), you can't hide such mispredictions anymore and it is probably better to just resync everything with a big jump even though I have seen games where everything turns into turbo mode for a short time.
If you've built one of these games, what sort of information is sent by your local game to the game server, and what sort of information is sent to you by the game server?
A player only needs to send changes in his direct actions to the server (movements, firing, using stuff). He might send additional data on how his computer predicts the outcome of his actions (who/what did he hit), but this depends on how your network system handles latency related conflicts. The server, on the other hand, only needs to send data to a player that does affect him and what he sees, and that invalidates previous updates the client got.
Generally, you only need to update the state of moveable objects over the network if their behavior changes in a way a computer can't predict with the information he has. For example changes in animation state, velocity, movement direction, etc. Additionally, you only need to update the data if it is relevant for the client.
You might also perform resyncs for every object from time to time to avoid obvious jumps due to the accumulation of small prediction errors, but depending on the object and your game this can be done at very low frequencies so that it doesn't affect the network traffic significantly.