A popular payment solution built into Magento is PayPal.  It is also a PCI compliant solution

An overview of integrated PayPal solutions are available at:
http://magento.com/paypal/complete-payment-solutions

PayPal options Comparison Chart:
http://magento.com/paypal/comparison-chart

PayPal merchant fees:
https://www.paypal.com/us/webapps/mpp/merchant-fees

All the latest PayPal integrated options are bundled with PayPal Express checkout, which is a highly recommended payment option for all stores.

The Authorize.net payment gateway is another popular choice.  Magento supports both the AIM and Direct Post methods.  The Direct Post method allows for easier PCI compliance, as the transaction is not passed through the Magento software.

In addition to real-time payment processors, the standard install of Magento CE also includes several offline payment options including Saved Credit Cards (not recommended), Check, Money Order, Purchase Order, etc…

Offline Credit Cards:
http://www.magentocommerce.com/knowledge-base/entry/how-can-i-capture-credit-card-information-without-a-payment-gateway1

Checks and Money Orders:
http://www.magentocommerce.com/knowledge-base/entry/how-do-i-accept-checks-and-money-orders-as-payment