Ouch, this has always been a touch subject for me as well. I've never
quite felt comfortable with a philosophy on when to use Exceptions and
when to not use them. Perhaps its just one of the many brain blocks I
have been blessed with.
You're not alone 
Perhaps these 5 points may be of some help:
* Exceptions are expensive to use. They can, in some cases materially,
affect the performance of your applicaiton. Unwinding the stack hurts.
I don't think this is really a problem for this particular app, as
this function is limited to the backend and there won't be much going
on at first.
* Exceptions should be used for just that, exceptions. An exceptional
condition is perhaps trying to allocate memory for a new object but it
just doesn't happen. That's definitely exceptional. 
Yeah, I see where your coming from. I suppose that's what I was really
asking. The thing is that the button or whatever that activates this
action won't be visible if the order has been cancelled. So, it
someone tries to ship it, is that exceptional? I'm on the fence
really.
* Use checks, of a return value or 'global' (ack) indicator, when
possible or prudent. I prefer to see a check for success or failure
than to rely on too many exceptions. Part of that can be due to my old
COM programming days on Windows (don't tell anyone I admitted to that).
* Catch the exception/error as soon as possible. React/log the gory
details and then push up if necessary with more generalized
information.
If I simply return true or false, how can I see what caused the record
update to fail. For instance, I may want to extend my example to the
below. Tell me if this is crazy 
class Order << AR:B
def mark_as_shipped
if self.status == 'cancelled'
raise OrderCancelledException
end
if self.status == 'unpaid'
raise OrderUnpaidException
end
# do shipping stuff
save
end
end
When I call the controller method and the update fails, if I just use
a return value I won't know from the controller, why it failed.
* Relying on exceptions too much can get ugly to read. Personally I
find it hard to read code that uses exception catches all over the
place. But then again, that's just me.
I don't think I've written or read enough code to call that yet 
I could see going both ways in your example. The <mark_as_shipped>
method sets an expected change of state to the object. Simple enough,
but if it doesn't work the caller may wish to know that's the case -
throw an exception. However, if this isn't THAT exceptional perhaps
you could consider a return value of the state. The caller can check
to see if the state was indeed changed to what was expected. Maybe
even just use true/false return value for success or failure. Its
possible some callers (perhaps a batch process) may not care. if so,
why force a call to wrap it in a rescue block?
If someone calls the mark_as_shipped without the order being ready to
ship, that should be exceptional as they shouldn't have the ability to
do that through the interface. I think.
So, while I didn't exactly answer the question I hope that gave you
some thoughts from someone who doesn't claim to know much about the
subject at all. 
Oh yes, thanks for your input 