Cryptography is rarely the right tool for privacy issues. Here, the trash bins are listening for the broadcast of MAC addresses by WiFi enabled devices, in particular phones. The tracking part is made possible due to the combination of several parameters:
WiFi-enabled devices broadcast data regularly. This is rather unavoidable: for WiFi to actually occur, either the device or the access point must talk first. Since there are "hidden" access points who do not talk until specifically addressed, the devices must blabber about constantly.
MAC addresses are fixed. An important point of MAC addresses is their uniqueness: things must be so that no two "unaltered" devices may use the same MAC address simultaneously, on the same local network. To ensure this uniqueness, a global allocation scheme has been designed, with hardware vendors being allocated address ranges. It is possible to force a MAC address change on most hardware, but this is "frowned upon".
People don't switch off the WiFi when not at home. They should (in particular, not using WiFi extends battery life), but they do not.
In the example, the trash bins just listen to all the broadcasting, and correlate data between each other, thus "tracking" the whereabouts of phones (and thus, presumably, of phone owners). A lone bin would not get much interesting data, but a lot of bins can come up, together, with a rather thorough map of movement behaviour of people. Note that the MAC address cannot be traced back to an owner identity, but it can, at least, uncover the hardware vendor name, because of the global MAC allocation system, which is public.
What could be done, assuming that we are free to define new protocols, is to replace the fixed 48-bit MAC addresses with random 128-bit addresses (regenerated frequently, e.g. every minute will not actually connected to an access point). Random addresses of 128 bits ensure uniqueness with sufficiently high probability, even if lots of devices are happen to be in the same location. For instance, if you have a stadium full of 60000 people, each with a phone, and they all try to do WiFi, 128-bit random MAC addresses would allow a collision to occur with probability about 2-97, i.e. "won't happen". But here we are talking about defining a new WiFi protocol and hoping for all devices and access points to simply switch to it, forfeiting any attempt at compatibility with existing WiFi access points. This kind of change is unlikely to occur within the next few years.
In the meantime, if you value your privacy, then simply shut down the WiFi !