There is no point in having an online store if you do not accept money from your customers. Deciding how you will get paid truly involves every single aspect of my 4 parts of developing an E-Commerce presence. I always tell my clients to give their customers as many ways to give them money as possible. The simplest is snail mail, where they will send you cash, check or money order through the mail. The next step up is taking credit cards over the phone, but that is so 1992 and will most likely scare the customer away.
When first starting out I recommend just accepting PayPal. The reason being is there is very low overhead, their API is easy to work with (just stay away from PayPal Pro) and they are a very recognized brand. It gives customers several ways to pay and through a trusted source. I will try to post an article on accepting payments through PayPal fairly soon to demonstrate how easy it is. They have two mechanisms to interface to their system, one is completely on the back-end, the other involves the client actually leaving your site and going to PayPal's checkout system.
Personally I do not recommend the later choice, unless you are in the very, very early stages of starting up and you want to get something online as fast as possible. It is never a good idea to take your customer away from your site for any reason and since PayPal has a good back-end API I recommend using it and keeping your site seamless.
The next step in accepting payments is to add, not replace PayPal, a real merchant gateway. The de facto standard way to accept payments online is with Credit and Debit cards. You can also accept Check or ACH payments too, but with the popularity of bank Debit cards this is becoming less and less available.
I recommend Authorize.net to my clients. I have worked with them since I started doing Web sites professionally. They have a very easy to use programming interface and have proven to be reliable over the years. There are several ways they work for E-Commerce clients. They can provide the full merchant account or a gateway to an existing merchant account. Either way programming against Authorize.net is the same.
If you are not familiar with the way merchant account work it is very simple. The actual interface from the machine you swipe your card through is known as the gateway. On the communication mechanism used by the web the form you fill out with the information is the gateway. The gateway actually sends the request across a secure channel to your bank's merchant system and gives it the information to process the request. The response, accepted or declined then bubbles back up to through the gateway to the site and you can then let the customer know the outcome of their transaction. For clients that have existing merchant accounts in place I recommend just the gateway product, but if you do not have anything in place I have them get the entire solution, it cost the same either way.
While Authorize.net is not the only solution out there I just like it the best. PayPal bought PayFlowPro from Verisign a couple of years ago. I also have worked with it and found it to be easy to work with as well. If you do a quick search for merchant accounts you will find many, many options. Be careful in selecting a solution because too often they will actually be rip offs, especially the cheaper offerings. I have also found that working with your traditional banks for online merchant accounts is a mistake too. My experience has been they want to charge massive fees for even the smallest store and often make it extremely complicated to program against their systems.
The main point is to find something that fits your business at the stage you are currently in. It is also wise to work with a solution that can easily be maintained and extended when needed. You should also make sure that each customer has as many ways to pay you, thus making them more comfortable giving you their hard earned money. Finally make the process as painless as possible.