They don't, actually. You just need a credit card to buy via PayPal. Having an account is optional.
There are lots of different cart options, so which you choose depends a lot on the need. There are carts that you build into your own site, but then you need an SSL cert etc. which can get a bit heavy duty. Or, as you note, there are third party carts, where the whole site is hosted by that third party. Then there are other like PayPal, where the buy now buttons are on your own site but the payment process is handled by a third party. These are my favorite. I've used a few, like Foxy Cart and FastSpring, but there are lots more. If the client is selling not too many products, my current favorite is GumRoad. It's simple, works really well and looks great, and you don't need rotten middle men like gateways and merchant accounts, which is great.