Solution
Open Terminal, and run the following:
xcode-select --install
This will pop a dialogue box, Select "Install", and it will download and install the Command Line Tools package and fix the problem.
(The popped Window may be behind other windows.)
You do not need Xcode, you can install only the Command Line Tools here, it is about 130 MB (600 MB as of Xcode v14.1).
If the above alone doesn't do it, then also run:
sudo xcode-select --reset
Further reading
The problem is that one needs to explicitly agree to the license agreement. As a follow on step, you may need to reset the path to Xcode if you have several versions or want the command line tools to run without Xcode.
sudo xcode-select --switch /Applications/Xcode.app
sudo xcode-select --switch /Library/Developer/CommandLineTools
I found the solution in this question, Command Line Tools not working.
You may get an error message: "Can't install the software because it is not currently available from the Software Update server". In this case xcode-select --reset
works as pointed by akozin.