You're on the right track. One dictionary says that the definition is:
the level of awareness in the minds of consumers that a particular product commands
A mindshare leader, then, is the company which commands the highest level of this awareness. A company which is a mindshare leader will be the first name you think of when you picture a given product; the company and the product become synonymous. Wikipedia gives some great examples of these leaders. The top example is Google: when you run an internet search, you might say you're googling, whether or not you use Google.com specifically. Other examples are Kleenex, Bandaids, and Tupperware.
To address your question about Microsoft: I would say that yes, Microsoft is a mind-share leader for operating systems. When I think of computers, it will be a Windows OS that comes to mind.