3460
Answer: Let me strengthen this insightful question. We find sources that positive minhagim are more identifiable than minhagim of refraining. The gemara (Pesachim 55a) deals with the possibility that refraining, for religious purposes, from something in front of others who believe it is permitted is yohara (haughtiness). The gemara says, though, that when one whose minhag is to not work on Tisha B’Av refrains from work in front of those who do, no one takes offense because onlookers will say that he is idle because he happens to not have work to do. Similarly, when one, for example, refrains from eating a certain food due to kashrut concerns, the "non-act" of not eating is not like a clear, noticeable, countable religious practice. Can one count three occurrences of not doing something?
This being argued, there is a concept of those who are bound to a practice of refraining from action and that this is an extension of the concept of neder (Nedarim 15a). This is likely a Rabbinic obligation (Tosafot ad loc.), although significant opinions hold it is a Torah law (see presentation in Kol Nidrei 72:5).
Your reference to three times is arguably a popularly held mistake. The classical Rishonim and the Shulchan Aruch (Yoreh Deah 214:1) do not mention a need for three times to be binding. On the other hand, besides mention of the text of Hatarat Nedarim, many Acharonim mention three times. The standard way of dealing with the apparent contradiction is as follows. If one intends the practice to be binding, it becomes so even after one time. If he did not have clear intention as to whether or not it be permanent, then three occurrences make it the norm, and therefore automatically binding (Shulchan Aruch Harav, Orach Chayim 468:17; Kaf Hachayim, OC 417:25).
Now to get to your question – how does doing an inaction (whether three times or once) become binding? I did not find this question discussed where one might expect it. We must determine what this dearth of sources means here (see Living the Halachic Process, V, G-1). Apparently, refraining from something for religious reasons does not need special requirements to be halachically significant. Let us consider that a neder is a matter between a person and Hashem and that since Halacha extends it to occurring without verbalization, it does not need to be clear to others what he was thinking. So if one was in a situation that he would have done X and he did not do so for a religious reason, this is equivalent in our context to actually performing a mitzva.
This same concept is behind the fulfillment of negative commandments in general. Every moment one does not sin is not a mitzva of refraining for which he receives reward but is neutral. However, if he is tempted to do an aveira (e.g., eat non-kosher food, drive somewhere on Shabbat.) but is refraining because of the mitzva to do so, he does receive reward (Kiddushin 39b). In such a case, refraining, beyond the letter of the law, from something one wants, creates a neder.
What is a little trickier is the following. Sometimes a person refrains from something, not out of a full decision, but because of "why not?" Let’s say that when he goes to a store and there is chalav Yisrael milk and regular milk, he purposely picks the chalav Yisrael. If he thought that he will henceforth only have chalav Yisrael, this should be binding. But it could also be that if he were in a place that the only milk is regular, he would buy that as well. Is that considered refraining from something? While it is hard to know where to draw the line, there might be a difference between three positive acts and three acts of refraining that are not necessarily indicative of his future plans.

Pizza, Pretzels and Pastry
Rabbi Yirmiyohu Kaganoff
The Laws of Torah Study
Part 3
Rabbi Eliezer Melamed | 5761

Using a Hand Masher for Cooked Vegetables
Rabbi Daniel Mann | Shvat 5773
Parshat Emor
What's in a Word?
Rabbi Zalman Baruch Melamed | Iyar 5761
Daf Yomi Makkot Daf 20
R' Eli Stefansky | 30 Nisan 5785
