Solved it.
So as GitHub Desktop was complaining about not being able to find gpg (I had installed it via homebrew), I figured there should be a way to tell git the exact path of gpg, turns out there is:
gpg.program
Use this custom program instead of “gpg” found on $PATH when making or verifying a PGP signature. The program must support the same command-line interface as GPG, namely, to verify a detached signature, “gpg –verify $file – <$signature” is run, and the program is expected to signal a good signature by exiting with code 0, and to generate an ASCII-armored detached signature, the standard input of “gpg -bsau $key” is fed with the contents to be signed, and the program is expected to send the result to its standard output.
https://git-scm.com/docs/git-config
So running the following solved the problem:
git config --global gpg.program "$(which gpg)"
GitHub got back to me and said that some users also need to use:
echo "no-tty" >> ~/.gnupg/gpg.conf