How does a Minhag become a Minhag? More specific is it possible to enact new Minhagim in todays generation?
There are 2 types of minhagim (at least):
Many "minhagim" are halacha, but varying communities will follow different rulings based on the Rav's psak. Many new minhagim of this nature start because a new Rabbi comes to town and changes the custom of which psak to follow. I have seen this happen in a number of places. Right or wrong, the custom becomes significant enough that people who come to town should not act differently- like the evolution of any halacha. (Of course the minhag may only apply until the next Rabbi comes to town.
The other type of minhag enhances other mitzvos. Many minhagim are in the process of development simply because they are brought in the Mishna Berurah. How many people do we see giving tzedaka during v'atta moshel bakol because the MB mentioned that the ARI did it? Or how about minhagim that came about through tziyonut?
In short, minhag is whatever people do and these can change at any time.
The story about the mikva is a legend concerning the Rema in Krakow.
The story is that the owner of the mikva (!) would tell them men "mazal tov" after their wives were tovel. When the Rema was appointed rav of Krakow, his first action was to instruct this man to stop it, since he was certain this was a terrible practice. A man who hadn't heard that the rav abolished it went to the man and asked him why he didn't say mazal tov; his wife was tovel the night before. The man answered that it was for two reasons: One, the Rema told him not to, and two, your wife didn't come last night - the implication being that she knew she could get away with skipping the mikva now without getting caught. And, goes the story, then the Rema realized the importance of minhag and resolved to collect the minhagim of Ashkenaz. This story is brought in the beginning of Lev Haivri, and IIRC was supposedly in the Krakow Pinkas.