I'd start by building a hypothesis of who your user would be - then go out and find some people that match that criteria. Landing pages & 'smoke tests' are some tools you can use to augment the info you gather, but you'll want to "get out of the building" and speak one on one with some potential users.
Also, when you're speaking with someone don't even bring up your product until the end. Focus on the problem that you're trying to solve.
I recently saw Brant Cooper and Patrick Vlaskovits speak, and would really recommend their book to anyone wanting to do customer development: http://www.custdev.com
