Also, while they're very similar in a mechanical sense since they're both about randomly generated test inputs, in a broader sense my impression is that fuzzers have a very different focus from property-based testing. I think fuzz testing typically refers to testing very complex software, like compilers, interpreters, and virtual machines, and searching for crazy edge cases, especially ones that may expose security vulnerabilities. So a lot of effort goes into generating test inputs that are unlikely to happen with a naive testing strategy (automated or manual), yet still interesting and relatively likely to trigger a bug (rather than spending too much time in the very large space of uninteresting test inputs that a naive testing strategy wouldn't come up with but also is unlikely to trigger a bug).
By contrast, I think property-based testing is typically used for testing programs that are of ordinary complexity, and quickly finding bugs due to simple but common programmer errors, which can then be quickly fixed. So a lot of effort goes into reducing any bugs that are found to the very minimal test case, which if the test input type is a nontrivial data structure can be surprisingly involved. MacIver has actually written a series of blogposts on Hypothesis' approach: http://hypothesis.works/articles/compositional-shrinking/