Payment Gateway: You probably already do card processing with a company (electronically through a payment gateway via card strip reader or PC app), find out if they offer an online gateway as part of their current plan you have with them. Some places include it, some places try to get more money out of you.
The spot for customers to enter their billing & shipping is built into the software. You only have to provide an SSL certificate to make sure that nobody snoops their info while typing it into your site. SSL certs are essentially free, what you pay for is the ability for the ssl provider to verify you are who you say you are to the customer on your website, so they feel safe about inputting their credit card #. It's surprising how many people actually don't even look to see if a site is secured or not. :sick: But regardless you will likely be bound by your payment gateway processor's agreements to provide an SSL Cert.
Very basically, an SSL connection encrypts the connection between the users computer and your website so Mr. Joe Wanna-be Hacker sitting next door connected to the customers open wireless, watching his internet traffic stream by can't read the data being passed between the user and the website and steal the users credit card info. Without an SSL connection, guess what... all your traffic is plain text and can be sniffed very easily if somebody were so inclined. That's also why it's important to have your wireless encrypted but that's a different subject.
Software: Many of them are free because they are based on open source. Most of which you can trust even more than many "paid" software because the code is open to view to any developer who wishes to look through it. Just because you pay for software doesn't mean it's any good.
I'm a huge fan of open source software in most cases. Places like this monetize through offering paid support and help. Magento does the same but the also now have an enterprise version that includes some things they decided not to include in their "open" version.
The only thing I can really recommend to take away some of the biggest headaches of setting this up would be to make sure your current card processor is compatible or has "modules" available for the cart software you decide to go with. I've had to have people switch processors just to make it easy on my end and get it done with... most of the time saving money for them too.
If you need more info, feel free to call me anytime. Else-wise I'll try to keep answering in this thread too.