Fuzz testing or Fuzzing is a software testing technique, which basically consists in finding implementation bugs using malformed/semi-malformed data injection.
A trivial example:
Lets's say there's a integer variable in a program, which results of a user's choice between 3 questions. When the user picks one choice, the choice will be transmitted to the program under a variable, say 0, 1 or 2. Which makes 3 practical cases. But what if we transmit 3, or 255 ? We can, because integers are stored in values which allow them to take a lot of cases (often more than necessary).
If the programmer is lazy, he may have taken no/less attention to the default switch case.
If so, the program may crash, which leads to "classical" security issues: (un)exploitable buffer overflows, simple DoS, ...
In these perspectives, Fuzzing is the "art" of automatically finding this type of implementation failures, and eventually being able to measure the found vulnerability dangerosity, and of course locate it (in order to exploit it).
Fuzzing is a type of Black Box Testing, which means testing a closed system on the comportemental point of view.
A fuzzer is a program which will inject semi-random data into a program/stack. Every "efficient" fuzzer is:
- protocol/file-format dependant
- data-type dependant
Why? Because a program only understands structured-enough data. If you connect to a web server in a raw way, it will only respond to listed commands such as GET (or eventually crash). If you try totally random inputs, it will in most cases respond with a "non-implemented method" error.
Take a 10 chars long string, supposed to fuzz a webserver: we generate all the possible strings doable within this string. It makes a lot of possibilities, right? What are the odds that you find the ones that start with "GET " ?
That's why a fuzzer has to understand at least the basics of a protocol / file format.
About explorable solutions space: comparison with Cryptanalysis
The number of possible tryable solutions is the explorable solutions space.
The aim of Cryptanalysis is to reduce this so called space, which means finding a way of having less keys to try than pure bruteforce to decrypt something.
In this regard, Fuzzers try to reduce the number of unuseful tests: the values we already know that here's little chance they'll work.
There's a big difference with Crypto though: the more "intelligent" your fuzzer is, the less weird errors it will find: you reduce impredictibility, in favor of speed. That's a compromise.
A fuzzer would try combinations of: - numbers (signed/unsigned integers/float...) - metadata : text-valuable information (mostly text) - the protocol/file format itself
A quick way (and common approach) to fuzzing is, for each types of data defined here, to define lists of "known-to-be-dangerous values" (fuzz vectors), and to inject them in place of the classical values.
Technical resources on OWASP
Fuzzing vectors 
Wikipedia article 
Fuzzing-related papers 
Fuzzer lists (mostly open sourced)
The ultimate fuzzers list @ infosec 
Another list @ hacksafe 
Codenomicon's product suite: