If the problem is just that it doesn't find the headers, then you can fix the problem by installing your distro's kernel-source package.
If you're getting a "compiler version mismatch" message in your nvidia-installer.log file (which is in /var/log), and if you are using Debian, then yes, you should recompile your kernel, as the Debian default kernel (in Woody at least) was compiled with an extremely old version of gcc, that isn't even installed in Woody anymore.
If you're getting compiler mismatches and you don't use Debian, though, then look into /proc/version and gcc -dumpversion to see which is newer. You may be able to fix the problem by upgrading gcc, or installing it if it isn't. Post the contentst of /proc/version and the output of gcc -dumpversion, too.