What are the different ways to make users (especially paranoid one's like me) feel safe about the security aspect of the site?
In general, having a well designed site will give a sense of security. If the site looks like has been thrown together in a couple of hours, it is not going to inspire much trust in the user. Compare the 2 sites below, which looks more trustworthy?
You can also increase the appearance of trust by adding icons related to security. Although they don't actually prove security, they have been shown to increase trust in the user.
Implementing testimonials about your products or services have been in A/B tests to increase conversions as they add credibility to your website.
Having a physical address or a phone number people can call will add to the trustworthiness of your site. If they can call you up and talk to a real person, it gives the user the sense that this is a real business, and not a scam site.
Buy and add a SSL certificate to your site, as some people look at for https:// in the url bar.
Both Richard Tan and FrankL's responses are great. I'd like to also add that something I've always found to reduce 'online safety paranoia' are simply: