The concept of a replay function goes waaaay back, long before computers were anywhere near powerful enough to just record video. The idea is that you just maintain a rolling recording of all the "events" that happen in the game. Largely, each frame (or some subdivision thereof) you record the position and orientation data of all the objects in the game, and then later, you can play the whole scene back, non-interactively, but you can view it from any angle, because it's not actually video.
In games that support networking, there's already a reasonable mechanic for this. All of that data is already being encoded, and compressed, to take up as little data as possible for the purpose of network performance. All you need to do, then, is to record all of your network traffic to disk. You can include a little extra stuff that isn't sent, like detailed control inputs and such, just to give a little extra detail and smoothness on playback.