Most importantly, the program should be good. If this is not good, no one will use it. You cannot hope that the chicken and the egg will be canceled and people will take it for granted until it becomes good.
Of course, “good” simply means “better than any other practical option for a significant number of people”, this does not mean that it is strictly the best, only that it has some functions that make it, for many people, better than other options. Sometimes a program has no equivalent anywhere, and in this case there are almost no requirements in this regard.
When a program is good, people will use it. Obviously, it should have a market among users - a good program that does something that no one wants, is not very good no matter how well designed it is. One could talk about marketing, but really good products, up to a point, tend to market. It is much more difficult to promote something bad, so clearly the product itself, and not the promotion of the product, should be one of the first priorities.
The real question then is how do you do it well? And the answer is a dedicated, experienced development team. One person rarely can create a good product on their own; even if they are much better than other developers, several perspectives have an incredibly beneficial impact on the project. That's why corporate sponsors are so helpful - it puts other developers (from the corporation) minds on the problem to give their own opinion. This is especially useful if program development requires significant knowledge that is not usually available in the community.
Of course, I say this all from experience. I am one of the main developers on x264 (currently the most active), one of the most popular video encoders. We have two main developers, various small community developers who provide patches and corporate sponsorship from Joost (Gabriel Bouvigne, which supports speed control algorithms), from Avail Media (who I sometimes work on contract and who currently hire coders for contract to add support for interlaced scanning MBAFF) and from several others that appear from time to time.
One good developer does not do a project - many good developers do. And the end result of this is a program that encodes video faster and has much better quality than most commercial competitors, hardware or software, even those with extremely huge development budgets.