United:

Domestic: Yes, on any published fare.
International: Yes on Full and "Select" discount fares (not the real cheapies).

United does both domestic and international upgrades using miles from your account almost exclusively electronically. Even at the last minute at the gate they can upgrade you and take the miles from your account. I just called and they still do issue the "paper" type certificates using your miles, and they are good for 1 year from date of issue. But the agent told me hardly anyone does this anymore.