1. Register a business (Ltd, LLC, etc)
2. Open a Business Bank Account
3. Implement Paypal to get yourself up and running,
4. Prove that there's a market for your product, people will pay for it, people will continue to pay for it, you don't have lots of chargebacks, you're capable of managing sensible customer relations, and generally are as small a risk as possible for any merchant account. As a bonus, this also validates your business plan before you invest too much time in irrelevant admin.
5. Go and talk to your bank. And every other bank out there. Shop around, shop around, shop around.
(As an aside, read David Mytton's blog: http://blog.boxedice.com/2009/05/20/taking-payments-online-m... )
6. Profit!
EDIT: fixed formatting