I would say that there is a discount on the shoes or that the price was discounted $25. Or to make things more complicated that the price was discounted by $25. I would say that the shoes were on sale rather than on discount.
For sale meaning available for purchase, On sale meaning that the shoes were on sale at a discount.
Is there a rule or is it merely regional usage?