I ran into the same issues trying to install audite. Turns out that mkmf writes a file call mkmf.log to tell you more specifically what it does to find out if the headers are availbale or not:
>>> cat mkmf.log
have_header: checking for mpg123.h... -------------------- no
"xcrun cc -E -I. -I/System/Library/Frameworks/Ruby.framework/Versions/1.8/usr/lib/ruby/1.8/universal-darwin12.0 -I. -D_XOPEN_SOURCE -D_DARWIN_C_SOURCE -g -Os -pipe -fno-common -DENABLE_DTRACE -fno-common -pipe -fno-common conftest.c -o conftest.i"
xcode-select: Error: No Xcode is selected. Use xcode-select -switch <path-to-xcode>, or see the xcode-select manpage (man xcode-select) for further information.
checked program was:
/* begin */
1: #include <mpg123.h>
/* end */
--------------------
Turns out that I hadn't had xcode installed yet; after installing it and running
xcode-select --print-path
I saw that the path was now set. Then I still had to run xcrun once to agree to Apple's licence agreements, but then the installed installed just fine!