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 an 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:
Including a friendly spinner to indicate page loads or server requests. I find users are easily agitated if they find themselves sitting and waiting for too long on a site where they are still deciding whether or not they can trust it with their wallets. A spinner can assure that something they've triggered is retrieving a response; much in the same way a phone operator will announce that they'll "Just look that up for you, sir.", or a sales clerk answers "No worries, right this way!" - At least it allures to stronger security and they don't think the delay is because their information has been sniffed somewhere along the line.
To add to the previous point - helpful error messages. If your site/application spits out messages like "Oops! Something's gone wrong. We're not sure what, but try again!", it's not going to strengthen faith in users the same way that a message like, "The details couldn't be submitted just yet - Check your connection and give it another try."
Depending on the type of business/service - A live chat. If at any point a user is confused or just needs clarity, having someone at their finger tips ready to answer anything will help strengthen their sense of security. They may not even need to use it, but just the presence of one will instill a little more confidence into those that needed it. I suppose it's similar to the psychology behind security cameras, knowing what you're doing is being monitored can help make you feel safe.
Testimonials. Real people with real opinions on your service instilling reassurance. Take it a step further and allow Facebook comments as part of the testimonial feed. If a user still had their doubts it's pretty hard to fake a Facebook profile for every testimonial and that will help put the ball back in your court.