For example, suppose I have a Product class that I can add to a shopping cart. I may want to be able to package it together with another item when it is also in the cart and add a 15% discount.
Should the product class be decorated with a new subclass allowing deals, or should product class be redesigned to allow the cart attach a price reduction "strategy" object to the Product, reducing the price?
This is an abstract example, so take it where you will.
just look at your domain.
if it is product which allows its price reduction (hm... i don't think so) then you should add it to product. if it is order (imo, the right place to do discounts) then it should be there.
Decorator is one of the least invasive patterns you can apply - when you do so, you follow the Open/Closed Principle because your original class is never modified. I tend to use Decorator whenever possible. This is mostly the case when the original class doesn't need to interact with the extension.
Injecting a Strategy is more invasive because the class getting the Strategy must be modified to accept the Strategy (obviously, once you have made this modification, you can apply lots of different Strategies without further modifying your class). I use Strategy when the original class needs to interact with the Strategy (e.g. ask it about something).
Note that Strategies can often be Decorated...