GGPO required the game to output save states. So at one point during the game loop, it needs to take a snapshot of everything in some form, store. I'm kinda at a loss at how to explain how game loops work without writing an essay littered with code snippets though....
What you'll hear from most people is this then requires a "bottom up" solution. That is, when you are programming the logic of the game you need to keep in mind that the game must be generating save states. Not something you can tack on after the fact.
Not saying it isn't impossible, but definitely hard. If NRS managed to pull it off I'd be
extremely curious to learn how they did it via patching.
*edit*
Found an article on ge loops that gives a pretty good description
http://gamedevelopment.tutsplus.com/articles/gamedev-glossary-what-is-the-game-loop--gamedev-2469
So imagine instead of going from the update to draw step, you instead sometimes went from update, to another update (to resync), and then draw, based on some piece of logic. In non GGPO you don't need to do that. They're not out of sync because you waited until they were, at the expense of input delay