I'd like to add a feature where a user can record a video of the game that they're playing. How do I do this?
I have not implemented the solution to this particular problem personally, but I will try to suggest one. Of course any of the solutions will slow down your programm cardinally, but technically it is possible. So what is probably worth trying, that you could use pygame.image.tostring() on you current frame, then just write (append) every frame to a file. So that will be actually your video in a raw format. Now if you want some particular video format, you should just convert it, best way is to use ffmpeg (you can call it before game exit with certain parameters from your game with subprocess.Popen("ffmpeg ...")). The only problem here is that the user, who want to record in such a way, must have ffmpeg installed in the system, so that ffmpeg is callable from the shell commandline. Advantage of this approach - it should be quite fast and does not use much extra memory, since you encode only once (for example when the user stops recording or exits the game) from the binary stream. 

Edit: that is just a broad description, of course you should find out also the wright parameters for ffmpeg, such as frame count, size and so on, and of course delete the raw data, since it can be really big file.
How do you record a "game" (PyGame or Tk) into a video?