Catalina, Big Sur, etc. (As of 2020 and 2021)
Recent versions of macOS and Xcode (e.g. Catalina 10.15 and Xcode 12.2) definitely have this broken. Reinstalling Xcode and xcode-select --install did not help for me at all (the solutions already posted seem to be outdated). I did not want to use rvm because it may cause some annoying problems.
I did a workaround by manually making a symbolic link:
cd /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX11.1.sdk/System/Library/Frameworks/Ruby.framework/Versions/2.6/usr/include/ruby-2.6.0/ruby
ln -sf ../../../../Headers/ruby/config.h
where ruby/config.h can be found at:
/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX11.1.sdk/System/Library/Frameworks/Ruby.framework/Versions/2.6/Headers/ruby/config.h.
You should change SDK versions (e.g. 11.1 in the above example) accordingly to your current xcode installation.
It is also very likely that one runs into another error where .../universal-darwin19/ruby/config.h cannot be found (Commonmarker gem cannot be installed (needed for jekyll) macos). It can be quick-fixed as follows:
cd /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX11.1.sdk/System/Library/Frameworks/Ruby.framework/Versions/2.6/usr/include/ruby-2.6.0
ln -sf universal-darwin20 universal-darwin19