IP Lawyer here. Note: I am a lawyer, but I am not your lawyer.

Upon using your name in commerce you acquire common law trademark rights. Filing a trademark before you are actually using it in commerce requires filing an Intent To Use trademark application and will cost you a few thousand dollars in legal fees (or a hell of a lot more if you are doing international) - either that or you are doing it yourself with trademarkia, and, in that case, I wish you bon chance.

Try to choose a strong name, but be prepared to change it.

"Strong" means, in order: a completely made up word, a word that has nothing to do with the product being offered, a word that is suggestive but not decriptive of the product. For more information, look up the "abercrombie" test.
https://en.wikipedia.org/wiki/Abercrombie_%26_Fitch_Co._v._H....
http://berryentertainmentlaw.com/the-abercrombie-formulation...

If you want to search for competing marks, please note that this is an extremely technical process. You can try to search on TESS, but it is very difficult.
https://tess2.uspto.gov

Note that this is only US trademarks.

Additionally, if your question is "how do I know if my mark will be infringing?" The answer is "that is an extremely hard and expensive question to answer." The touchstone of trademark infringement is the "likelihood of consumer confusion test," which is ensconced in the sleekcraft / polaroid factors.
http://www3.ce9.uscourts.gov/jury-instructions/node/244
http://likelytocauseconfusion.com/likelihoodofconfusionfacto...

The point of all the above is that you really do need to be a professional at this in order to have the wherewithal to make judgments about the likelihood of a trademark's success. In addition, it takes a few business quarters to a year and a half for a registration to issue.

The point of all this is that domai.nr is as important a tool as TESS, that you can easily get lost in the weeds on this issue, that your own judgment is in no way a replacement or a substitute for a licensed attorney, that trademark strategy is hugely complicated and can be a total sinkhole. What does that mean? It means that, for a startup, like many, many other issues, you do the best you can but keep in mind that you are going to have to spend a lot of time and effort on it down the road.

Tl:dr:
As a startup in general: IF YOU HAVE THE MONEY, it is worth starting this process this sooner rather than later. If you do NOT have the money, a reasonable strategy is to move forward with a name that you like but are willing to change. It is okay to change your name very early on. However, the goal is to avoid having to change your name when you already have a product out and some market presence.
For YC: Do you need a trademark before you apply to YC? Almost definitely not - unless you are already selling your product. Do you need a trademark before you start selling your service to enterprises or spending money on marketing? It would be foolish not to at least engage an attorney and start the process.

Note that many other IP attorneys may have different opinions. That's fine - reasonable minds can differ on this subject, the above is an extremely short primer. Also please note that I AM NOT YOUR ATTORNEY AND IF YOU ARE THINKING ABOUT FILING A TRADEMARK YOU NEED AN ATTORNEY.

Edit: shoutout to https://news.ycombinator.com/user?id=27182818284 for posting this PG blog post - extremely on point: http://www.paulgraham.com/name.html