I've probably read that sentence at least 1000 times in a number of different books and articles. Having gone through a lean startup accelerator a few years ago when they were en vogue we focused on this aspect more than anything else.
The thing I never hear is how people actually figured that out. Cold calling, cold emailing, going to meetups, getting intros, pitching ideas and gathering feedback is never discussed. I want to hear _how_ you found a product market fit. It's obvious that you need to do this.
As an example. A startup that I co-founded my sophomore year in college was accepted into a school run summer business accelerator. They emphasized talking with customers/users more than anything else. The problem was we didn't really know any of our potential customers or users (grade school teachers/public schools). So we had to essentially cold call schools, find teachers/admins emails online, and fish around our personal network for intros. To say it didn't go well is an understatement. Our success rate, of even a phone call, was nearly 1% (roughly one answer per 100 or so emails/calls). We eventually locked down a core group of users simply by contacting so many people. Aside from other bureaucratic factors in the public schooling system we failed simply because we couldn't establish a growing user base.
So, if anyone wants to tell their story with nitty gitty details of not only how they found and retained their users but how they found what they wanted would be greatly appreciated.