Basically, HSTS allows a site to store a flag (true or false) - in other Words a bit, in a web browser.
Storing HSTS super cookies are accomplished in this way:
Lets say we want to store the value A, binary 01000001.
We can then store this as by redirecting the user to a series of websites, like
https://00.example.org indicating HSTS=off
redirecting to:
https://01.example.org indicating HSTS=on
redirecting to:
https://02.example.org indicating HSTS=off
...
...
redirecting to:
https://08.example.org indicating HSTS=on
"Reading" the cookie is simple as redirecting user to:
http://00.example.org
If HSTS is on, the webserver will receive a request to https://00.example.org, else http://00.example.org
redirect then to http://01.example.org
and so on.
The misdesign in HSTS is that the browser should "correct" a HTTP visit to HTTPS automatically if HSTS is enabled. A better idea would be that a HTTP request to a HSTS resource would instead fail completely with no recourse from the user other than manually typing https Before the url. But such things might endanger the usability.
No you dont need to worry. A site that wants to track you could aswell store your IP adress on server side to be able to show targeted ads and such. If you want to surf completely anonymously, for example via TOR, you should turn off HSTS completely, and instead itself be vary of SSLstrip by manually checking that HTTPS is being deployed.