You are being watched...
Retailers, crooks, the government, and others shady individuals are tracking your movements. Even when your Wi-Fi is turned off, your phone may be broadcasting information to whomever is in range which can be used both to track repeated visits to as well as your exact movements in an area under surveillance.
It's not a big step to couple this to personal information - a retailer for example, could track your trip to the register and correlate with your payment information. Now the tracking hardware and software vendors, the store (or chain) owner, their business partners, they can now all track where you are every time you come into range of one of their systems, and fully profile who you are, what you do, your financials, and your daily patterns!
That is just one example, but there are many uses for tracking you. Make no mistake, this is happening in the real world today.
One solution is shutting off Wi-Fi completely (including the background network scanning, a setting most people don't know about), but you would lose benefits like automatically connecting to known Wi-Fi networks and improved location awareness for your apps. It also does nothing to help the situation for others.
Pry-Fi will prevent your device from announcing all the networks it knows to the outside world, but it will still allow background scanning and automatically connecting to Wi-Fi networks. While you are not connected to a Wi-Fi network, the MAC address will constantly be pseudo-randomized, following a pattern that still makes the trackers think you are a real person, but they will not encounter your MAC address again. This will slowly poison their tracking database with useless information.
When you do connect to a Wi-Fi network, unless you specify otherwise, your MAC address will also be randomized - the same MAC address will not be used the next time you connect to this or any other network.
Though of course the companies involved with these trackers claim they wouldn't use the data maliciously, the possibility is there, and we all know that if something can be abused, ultimately it will be. There do not appear to be any laws against these practices yet, nor is it likely Wi-Fi will be redesigned any time soon to get rid of the information leaks.
But we can make an effort to reduce the usefulness of the tracking data for the exploiters. Pry-Fi comes with a War mode, which when enabled tries to make your Android device appear like dozens of people. Just wandering around an area under Wi-Fi location surveillance for a few minutes can ruin the tracking data for the period of your stay.
Proof of Concept
This is proof-of-concept code, and how for it will go in the future depends on interest and how well it works. It has been tested on several devices and seems to work, but it is very young still. The magic the app does to achieve its purpose is ever subject to changing Android security policies and OEM customizations, so even though it works now, there really is no saying if it will still be possible in future firmwares.
Of course you should also keep in mind that tracking can be done in many ways, and these W-Fi signals are far from the only method in use.
Further details, device compatibility information, FAQ, discussion, etc is all available on XDA-Developers.com here:
[APP][4.2+][2014.02.02] Pry-Fi v1.20 [ROOT] - xda-developers