The most common way such abilities are found is when an individual is put into a situation where even they do not know what the outcome will be, and fate (or probability, if you prefer) decides that they are going to invoke their abilities. Once it has been done, they will be left scratching their head, wondering how this occurred. This sets them up to go about a systematic learning process.
If there is a group of people know for such gifts, it would be reasonable for the culture to adapt to put its members into positions which are safe, but have unpredictable outcomes, giving one more opportunities to discover an innate gift.
As you said, the ability to wield magic is both powerful and rare which also makes it equally valuable. You said something that stuck out to me about one particular ability being that one could see magic. While being more of a passive power, it might be the greatest of all. If, assuming that magic is innate within the individual, these individuals could be trained to spot the signs of magic; the slightest trace of untrained and untamed power in others. Through their experience, they might be the ones who design the tests with which to root out magic wielders when they are young.