make and install for another machine
 

Problem I'm faced with all the time is installing an application on a machine that does not have gcc or kernel headers. Is there a way to compile on a machine with all the neccesary compiling software and then copy to a machine without it?

Yes by creating a binary package. Depending on which distro your using, will vary how easy each one is. Also if you know what files are being installed when you do a make install ( it should say when you runit ) You could just bundle them up in a tar file and copy them back into the dame location on the other machine.

"creating a binary package"
Google seems to think that this is the same as building an RPM package. ??? Is it the same or like a binary package and which one will deliver everything and not be left looking for a lib after installation.

RPM's are a binary package, so are Deb's Their the big two, will work its whats best for your distro, If its Debian based then a deb would be better, if its Redhat, Fedora, Suse, or one based on these it would probably be better with RPM.