These options have been recommended already, but here is my reasoning my I recommend each to my customer:

• PayPal (or Google Checkout or similar) is great for small websites. It's easy to setup and often they don't have a monthly charge, only a per transaction charge. But it can be confusing for the user as they'll be sent to a website that doesn't look like yours and people often get confused with PayPal because the link to pay without an account is small and hidden in the bottom left. You can also get the account and start using it all within 1 day.
• Full payment processor (my recommendation is Beanstream). When you want to integrate the payment solution directly into your website and have a full payment solution integrated into your site, this is the way to go. It will allow you a lot more flexibility and won't be as confusing for users. You can also do debit transactions. They usually have a monthly fee and do credit check. Some of them also have contracts. Within this option are 2 options:
  • using the payment processors payment page: this removes the requirement to go through additional security checks on the server. Most times you can format this page as you want and use their secure server to store image, CSS and JS.
  • take the credit card on your server and pass it to the payment processor, receiving the response back and doing the appropriate processes. This allows even more customization, but requires additional security checks and an SSL certificate.
• A subscription based shopping cart where they have a shopping cart and payment solution that you pay for on a monthly basis. This has the advantage of not having to do the integration yourself. But they are much less flexible than doing it yourself.

These are the 3 options I've worked with. I'm sure there are others.