It should be easy...a difficult part may be the database part. If your famiiar with setting up mysql databases on your server, then it should be a piece of cake. Modifying it is the hard part ...well not hard, but just time consuming and requires you to be able to read programming. I never programmed in PHP, but I can sure as hell read it which made it very easy for me to hack up.
As you can see mentioned in their Features list, Paypal is already supported by osCommerce, so I guess all you'd have to do is enable the Paypal processor, and fill in your paypal email address in order for the shopping cart to start accepting PP payments..
A basic install is easy. It's getting any of the various mods to actually work properly that can be a royal PIA.. One of the reasons I used zen-cart (it's a fork of OsC) was because the support you got in the forums was so much better. My .02..
cubecart is a bit simpler to operate IMO than oscommerce. but theyre both as easy/difficult to install. make it as hard as u want with different add ons.
osCommerce is very good, the basic installation is pretty simple (as long as you can use mysql databases)... It does get harder when you install addons and edits. Good luck with it
very easy to install, if you go for a vanilla install make sure you get the paypal ipn contribution if you don't there's serious issues with orders getting lost. if you want a templated oscommerce store send me a pm.
Also, it's even easier within Fantastico, just take a look at your cpanel if you have it. That way, you don't have to create the database yourself.