To accept credit cards online you typically need the following 3 components:
1. A merchant account: The two largest in the US are First Data/Paymentech and Nova. There are thousands upon thousands of resellers. You should not pay more than 2% of the transaction + about a quarter per transaction + a monthly fee - usually around $20. You will need to pass a credit check, as well as provide the processing bank with proof of financials. AMEX and Discover do not use resellers - you must apply directly. Their rates are about 1% or so higher than Visa/MC.
2. Payment Gateway: The largest is Verisign, then Authorize.net. The gateway acts as a virtual terminal. Your shopping cart will parse data through the gateway to charge or credit the card, or you can do so manually. The gateway also allows implementation of fraud protection features, such as AVS (address vertification system).
3. A shopping cart: There are thousands available. Many resellers of Visa/MC merchant accounts provide free basic carts. Make sure the cart you choose supports your payment gateway. It's more professional and less expensive to host your own shopping cart, rather than run it on a third party server. I recommend choosing a shopping cart that is SEO friendly - as you want the spiders to pick up the content stored in the cart.
I can write a whole book on the topic of accepting credit cards online. Above are the basics you should know to get started.
Very good post Avi, and all quite accurate. I would add to it, however, that a lot of the providers, systems and costs quoted by you only apply to US based businesses. Visa's cross-border acquiring regulations make it impossible for a business entitiy not incorporated in the US to have an acquiring account in the US, and most ACH (online check) providers will not deal with offshore companies either.
Basically, when a company is located outside the US there is an entirely new set of circumstances that apply. There are still plenty of merchant banks that deal with online processing in each VISA determined region, but the costs are quite different. There are a few ACH providers that will deal with offshore companies, but again, the rates are often higher, etc... (....and I could also go on to write a book here.

).