Where are you located?
Are your customers private individuals or businesses?
Whats the average order value?
What payment methods are you offering now?
I am located in UAE - Dubai.
Customers are mostly individuals, and the average order value is around 50 USD. The current payment methods are only through payment cards.
If the shop in question is your gift shop with 2checkout-interface (credit card and wire transfer) there's not much to add. PayPal maybe.
Paypal, Hyperwallet, Neteller, Bill me Later, Firepay, Wire, Cheque, Money Order, Amex, Discover, Delta, Maestro, Switch, Solo.
These are of course in addition to Visa and MC.
The more the merrier, just don't confuse your users come check out time.
Did I miss any?
Yes you did:
Just wanted to share some related information with you all;
"According to a recent study by CyberSource Corp., websites providing four or more payment methods other than credit cards have a sales conversion rate that's 12 percent higher than those offering just one payment option in addition to credit cards."
Ecommerce works better if it involves reliability.
Keep it simple. As an online shopper, I run when I see a zillion payment options (I'm in the US, btw)
Simple test: how many payment options does Wal-Mart offer? They know something about retailing.
Well, what type of payment methods are your customers requesting?