My recommendation? Look into FoxyCart, CS-Cart, Shopify, BigCommerce, Interspire - in that order. You will be very happy.
Pros - Beautiful themes out of the box - Easy to setup initially (i.e. payment plug-ins,etc)
Cons - Extremely slow on a shared host (i.e. netfirms) - If your host is slow, using the admin panel to manage the content is painful
The performance issue killed it for me. Unless you can spend some more money on a good hosting service, I'd stay away from it. Otherwise, it's pretty awesome out of the box.
http://www.expressionengine.com
I've also saw this recently, but haven't looked into it much beyond the web site. Might be worth taking a look:
You could try Open Cart, it's quite a modern PHP cart with paypal etc built in.