When it comes to naming your software *product* (whether an application or a library), what do you do?

It seems impossible to choose a name which isn't already taken by some other piece of software, whether it's someone's small hobby project or a company selling it. We all know about Phoenix becoming Firebird becoming Firefox because it clashed with other software product names.

How unique does a name have to be? Phoenix was the name of a computer BIOS - hardly similar to a web browser, wasn't it? And to take a counter-example, there's Fedora the operating system and Fedora the repository software, happily co-existing. Another counter-example is midori the Javascript framework and midori the web browser.

What steps would you take to ensure the name of your application or library isn't taken by someone else, and how far would you look - in terms of the type of product - when looking for other things with the same name?