Unlike standard cookies which can easily be controlled and cleaned by your respective browser, cookies set and used by Flash are a different animal altogether. Because Flash works outside of your browser, it has the ability to store cookies (aka LSO’s) in various folders throughout your system which is the foundation of how the "super cookie" you may have heard about works.
So essentially, when you are deleting browser cookies, Flash cookies are not deleted and can easily be "respawned" as browser cookies. To get rid of them, you have to clean them separately. Firefox offers the BetterPrivacy add-on which does this automatically, but if you don’t use Firefox a utility which can do this for you is the appropriately named Flash Cookies Cleaner. (As a side note, I believe CCleaner will remove Flash cookies, but I am not 100% sure.)
If you are concerned about your online privacy, cleaning Flash cookies has become a must.