It is an intensive process, takes a while, and is expensive. There are companies that do little else, and will charge you handsomely. The USPTO (Patents and Trademark office) has search facilities on its website that will allow you do search for yourself without a fee but considerable cost in time. I assume that similar facilities exist for other economic regions, but don't have experience with them.
The bottom line is that, like patent search, it takes care and time.
It's not all gloomy, though. The essence of trademark violation is that someone might confuse your brand with some already-registered competitor. In most cases, that means that you can narrow your search to companies in roughly the same line of business and (provided you don't do something egregious like using a nice curvy swoosh for your new line of athletic footwear) not have a problem.
For SMBs (small and medium businesses) with only a local presence, this is seldom much of an issue, but if you're a web startup or have national or international ambitions, it is highly recommended that you invest the time and money up front to avoid marketing embarrassment and/or legal expense later.