When using a phone while logged in to your accounts, you're visible.
I remember reading an article that a determined owner can track you between APs and thus know your location and routine. Now I found out that one can randomize one's MAC address, so I was wondering if that can prevent my identification and consequent tracking.
Spoofing your MAC address is trivial. Encryption here is irrelevant. It doesn't matter if they can't tell what you're communicating, so as long as they can identify you and know where you are.
Even changing your IP address and using random proxies can be used to identify you easily. How? It's very simple. You may be logged in to multiple Google / Apple services. When you log into those services, they store every single IP address that was used to connect to that account. Here's more information on how you can be tracked online:
It doesn't change the fact that your social media may be still active and gathering information about you. Your MAC address is less relevant than the device you hold, and it's accompanying identification plus accounts.
Assuming all communication between the client and the outside world is encrypted end-to-end.
The encryption doesn't matter if you're sending encrypted data to advertisers which they can decrypt, such as your device ID, known accounts, etc. They don't really need to know what you're doing - just that you're there. That's all they need to really dig into your life.
Throwaway Smartphone without your normal accounts = stealthy
With this method, the only way you can be identified and tracked is in person, through cameras, or if you decide to log into your own account(s).
In some rare cases, your smartphone could be hacked and the camera could be used to spy on you, especially if you get the attention of the wrong people. However, this is very unlikely unless you're a criminal of sorts.
Using a Laptop correctly = stealthy
With this method, it's the same as a throwaway smartphone, but you need a different Operating System than Windows. Without logging in to your normal accounts, you'll greatly reduce your footprint.
You don't want your operating system keys / device IDs to point back to you. Windows Update/etc will send information to Microsoft about you, including the IP address you were connected to at the time. If you're using the same windows key / hardware every time, then it'll be very easy to put the pieces of the puzzle together.
So who exactly is using this information, and how are they doing it?
It doesn't matter if you're using encryption: they can still tell you were there. Not using encryption is just icing on the cake. When you connect to WiFi hotspots, you agree to the terms of service. They will collect information about your device, and sell that information to third parties.
Third parties will take that information and use data analysis to correlate your usage patterns, how you travel, where you connect, etc. Remember that advertisement companies want data on you, as they're able to sell it to those who are interested in it.
With a big enough data set, it's easy to show correlations between where you are, where you've been, and which accounts or IP addresses accessed that information. Using your unique device IDs, it's rather easy to tie multiple pieces of information together.
Even if the company claims that they don't sell personal information about you, it quickly becomes personal information through data aggregation, analysis, and correlation.
Remember, if something is free, you are the product.
Too Long, Didn't Read
It won't really help you. At best, randomizing or changing your MAC address will give you a small layer of "protection," so as long as you don't use any of your normal accounts, and don't leak your device IDs.
However, there are too many other things working against you at this time. In every single case, you should note that most public places have cameras, so you will be identified.
Do you really need that much opsec? Who's after you? >:|