Pretty much exactly the same as networking works, except they store the gamestate in a buffer rather than send it to a remote client.
The replay is just the playback of that buffer.
The buffer, and your Networking, will track (at least) the location, orientation, and some sort of state information about every object which can effect the game state determinism at that point in time. Things which are purely visual and have no impact on the game itself are not typically stored. E.g: Barrels in racing games which bounce off the player car but do not change the physics of the car, or the objects in the world.
How much, and exactly what data you need to store will depend on how your engine works and how it deals with determinism. You can at worst store every single transform for every single animatable node in every single character if your engine sucks and doesn't handle determinism well. If you have a very solid engine, you can store much less data possibly even just controller input, which is how Starcraft replays work. The disadvantage is that you have to simulate the entire state from the beginning of the replay, and cannot quickly jump to different points in time.
So, the answer is "It Depends". It also depends on what your replay requirements are: Do you need to jump to certain points in the replay? Will you play them back linearly? Do you just want to capture the "fun" bits? (and that is an entire different question on its own).