Maybe it's just my affinity for taking a different approach, but my first thoughts about this question were a bit different than the great answers you have so far, so I'll put it out there.
Online trust isn't about badges, logos or expensive design. It's about simplicity of usability, transparency of motives, and all around consistency.
Simplicity:
Your visitors came to your site to accomplish something, don't bombard them with slick copy trying to prove your honesty. Help them do something great (what they came for) very easily and then reinforce your honesty and "brand" their experience as unique to your company. The old adage rings true: "Clothes don't make the man, they only amplify him, for better or worse."
Transparency:
As for transparency, trust is easy. It butts up directly with the foundation of a good business. If you're goal as a chef is to cook a great meal at a great price your goal is the same as the customer. Letting them know this creates trust because your needs are aligned. If you're entire goal is to make the highest profit-margin from your sales, good luck serving a great customer experience.
Consistency:
On first visit, make sure your copy says the same things all the way across the site. The quickest feeling of distrust comes from getting mixed messages. On repeat visits, make sure the experience and ability to complete the goal is as easy as the last time. Great sites use data collected from previous visits to make future experiences better and faster. Now you're building loyalty.
As an example, I used to use Pandora when I lived in the U.S. and it was so consistent on my computer and phone that it was beginning to feel like an appliance that replaced the radio. They had my complete online radio loyalty. Out of curiosity, I tried Last.fm for a bit and it was flaky and inconsistent (songs would change mid-way through). I subconsciously compared that to my experience with Pandora and it reinforced my loyalty to the superior product. Also to note, Pandora is sooo simple where Last.fm is quite a bit more complex (simplicity makes it easier to get consistency right).
Summary
Sorry if this post doesn't give you color schemes or layouts or any tangible tips you can use directly. It's intent is purely to help people get it.
Good Luck!