Naming a product is tough. It's thankless, there's no objective criteria for success, and when you're first starting out, it can seem unproductive. But none of these are legitimate excuses for not spending a tremendous amount of time and energy picking that name. Later on, when you have paying customers, the name that shows up on their credit card statements will be a soothing reminder of your consistent and trustworthy brand. Changing it requires far more effort than most founders imagine, so do it right the first time. Here's a concrete step-by-step guide to finding a great name for your startup's product.
Create a list of possible names.
There are dozens of excellent articles that can get you started with the process of brainstorming possible names. Most of these articles do an excellent job of summarizing the most common guidelines, so I will only briefly mention them here:
- The shorter the name, the better.
- Choose something that can be verbed. "I'm going to Twitter this" works much better than "I'm going to ShortMessagesWithFriends" this.
- Choose a relevant name, if you are starting an invoicing company, bikemanufacturers.com probably isn't appropriate.
- Choose names with greater phonetic clarity. The word "phonetic," for example is terrible because it isn't clear when spoken whether it should be spelled "fonetic," "phonetic," "fonetik," or "phonetik." The proliferation of mis-spelled domains and product names have exacerbated this problem.
- For products that create new markets (AirBnB for instance), it won't be important to have a name with high SEO value like "bestbnb.com." If search discoverability is important, however, consider shelling out cash for a name that will rank for your keywords. You can think of this as money well spent compared to the Adwords, conference attendance, and content marketing you would need to do later to drum up traffic for a less discoverable domain.
- If you are struggling to come up with ideas, I recommend using Impossibility, which has the added benefit of only showing you available, non-parked domains.
Check availability and price.
For my second startup, we generated about 150 possible names to start. My cofounders and I checked their availability using InstantDomainSearch, and weeded out names that both didn't excite us and were unavailable. Since we were creating a product that was unlikely to benefit a great deal from organic SEO, we disqualified quite a few domains that were selling for more than a few thousand dollars. 
Gather relevant data.
Next, my founders and I rated each name on a scale of 1-10. Using this data, we created an average score for each name that equally represented our preferences. We sorted the names using our aggregate scores and chose the top 15.
We then create a Google form, and sent the top 15 names to 30 people who were either potential customers, close friends, or both. The form asked recipients to rate the names using the same 1-10 scale.
Using the data from real potential customers and those who were heavily invested in our success, we created a final index of each each name's overall goodness.
Steve Blank says that products rarely survive first contact with customers, and the same is true of names. In our case, we had an internal favorite which was disliked by our friends and potential customers. If we hadn't sought feedback, we would have chosen a terrible name!
Contacting Domain Owners
Domain names can be shockingly expensive , but for most product-based companies, it doesn't make sense to spend very much on the domain. Quality products take thousands of hours to build, brand, and market. Invest your time in a new name rather than fighting the baggage left by the domain's previous owner.
After getting feedback about our choices, we disqualified the lowest five options and focused on getting one of the top ten names. Of those, only one was not registered, two were unwilling to sell, two did not return our inquiry email, and the remainder quoted prices ranging from $32,000 to $700. The audience favorite, however, was listed for $788, which we ended up purchasing.
Considering the costs associated with re-branding, it makes monetary sense to invest heavily in choosing the best available name. It took us 20-30 hours to make our decision, and among the tasks associated with getting a new business started, I count those hours as some of the most valuable.
 Interestingly, the most expensive domain we discovered had a "suggested retail price" of $80,000.
 For kicks, you might enjoy checking out the list of the most expensive domain names ever sold. The current king is $35.6M for insurance.com.