The cost of the second microphone can be substantial. The cost of the CPU power may not be. You can get a very long way in noise cancellation simply by placing the two mics near each other and subtracting the signal of one from the other. See the noise-canceling entry of http://en.wikipedia.org/wiki/Microphone#Application-specific... (the last paragraph in the "Application-specific designs).
You don't even need a CPU for that, you can do that with simple electronics. Noise-canceling headphones are freakishly complicated, directional (what is often meant by "noise canceling") microphones are possible with very simple designs.
I wish I could google up a piece on signal processing but my google search is getting dominated by things I can buy.
