I was looking forward to playing this game after I got home, however the progress I made on another PC did not register here, I got thrown back to the beginning of the game.
I used the other PC all day (with GoG Galaxy install ofc), it was connected to the internet, so I don't see a reason why the saves wouldn't be synced.

Is this a known issue or maybe something is wrong on my end?
Manually sending myself the saves every time would be annoying, but still better than not playing, however I couldn't find the saves on the usual locations (install folder, AppData, Documents..). Where does the game store them?

The game uses registry for pretty much everything, including save files, as described in one of the topics in this forum. You should export saves from registry to transfer them to other PC.