The way Google: ship it and make it work really, really well.
The product was so good that people noticed. They were able to take this and leverage this into being search for a really large property, like
Back in the 90s there were lots of search engines. People didn't pick Google because it was hard to switch, they converged on Google because the product was that good - there was Infoseek, HotBot, AskJeeves, Alta Vista, Lycos, Yahoo, Excite ... the list goes on.
It's a theoretical problem to have a significantly better search engine and not find users for it.