Where are keyboard shortcuts stored (for backup and sync purposes)?

The shortcuts that can be set in System Preferences > Keyboard > Shortcuts > App Shortcuts are stored in ~/Library/Preferences/.GlobalPreferences.plist and the property lists of applications (like ~/Library/Preferences/com.apple.iTunes.plist or ~/Library/Containers/com.apple.chess/Data/Library/Preferences/com.apple.chess.plist).

The shortcuts for services are stored in ~/Library/Preferences/pbs.plist.

As described in the accepted answer, you can determine an app's shortcuts by converting the plist to xml and then parsing the xml. You can also (tested on macOS Sierra 10.12.6) get the values directly with the defaults read command.

To write out the user key commands that apply in all applications run defaults read NSGlobalDomain NSUserKeyEquivalents:

$ defaults read NSGlobalDomain NSUserKeyEquivalents
{
    "Enter Full Screen" = "@^f";
    "Exit Full Screen" = "@^f";
    "Merge All Windows" = "@$m";
}

To write out the user keyboard shortcuts for a particular app, use defaults read <app-plist-name> NSUserKeyEquivalents. For example, to get the user keyboard shortcuts for Safari run (in this example, the user hasn't set any custom keyboard shortcuts for Safari)

$ defaults read com.apple.safari NSUserKeyEquivalents
The domain/default pair of (com.apple.safari, NSUserKeyEquivalents) does not exist

Key mappings I have discovered in this string syntax:

• command = @
• control = ^
• option = ~
• shift = $