How do different distributions modify the locations of config files for programs?
It depends on the distribution and the original ('upstream') source.
With most autoconf- and automake-using packages, it is possible to specify the directory where the configuration files will be looked for using the --sysconfdir parameter. Other build systems (e.g., CMake) have similar options. If the source package uses one of those build systems, then the packager can easily specify the right parameters, and no patches are required. Even if they don't (e.g., because the upstream source uses some home-grown build system), it's often still possible to specify some build configuration to move the config files to a particular location without having to patch the upstream source.
It that isn't the case, then often the distribution will indeed have to add patches to the source to make it move files in what they consider to be the 'right' location. In most cases, distribution packagers will then write a patch which will allow the source to be configured in the above sense, so that they can send the patch to the upstream maintainers, and don't have to keep maintaining/updating it. This is the case for configuration file locations, but also for other things, like the bin/sbin executables (the interpretation of what is a system administrator's command differs between distributions), location where to write documentation, and so on.
Side note: if you maintain some free software, please make it easy for packagers to talk to you. Otherwise we have to maintain such patches for no particularly good reason...
They have patches applied to the source code tree that adapt the locations.
There are enough "standards" available that every distribution can take their pick based on (personal) preferences and/or historical practises. There is seldom a solution that only has advantages. That is sometimes annoying/confusing, but consistency within one distribution is the most important objective: it leads to less clutter and easier guessing where things might be for program Y if you already know where similar things (setup/configuration files e.g) are for program X.
Example of patch application
My python package ruamel.yaml is available in Debian Sid. It used to be dependent on ruamel.base, and users who installed via PyPI might still have older, incompatible, versions of ruamel.base installed. Using setup.py/PyPI is no real package management, so you cannot delete a package previously installed through dependencies. I solved the issue for PyPI users by making a newer version of ruamel.base that removed the problems associated with older ruamel.base packages and made ruamel.yaml dependant on that newer version.
For Sid this is not a problem: older versions of ruamel.base were not installed (or could be removed through package management). Therefore they apply a patch, which you can find on the ruamel.yaml information page for Sid that removes the dependency of ruamel.yaml on ruamel.base.
Other distributions have similar setups. E.g. if you look at the specifications of creating a source RPM file (e.g for RedHat/CentOS/SuSE), you'll see that you combine the original original tarball of a package with one or more patches that will be applied before configuring/compiling.