For travelers in Ukraine, how common is it to be able to pay using Visa or Mastercard?
Are other cards, such as American Express/Discover commonly accepted? Any other caveats about paying by card in Ukraine?
I visited Ukraine about a month ago - Kyiv and Kharkiv mainly, but also a couple of smaller towns. In most large-ish stores, Visa and Mastercard were accepted. Pretty much all tourist/souvenir shops that I saw accepted them. All hotels accept them. Majority of restaurants accepted them. You can use them to purchase tickets for air and rail travel and most long-distance buses/coaches (although it did depend on where you were buying tickets). They were not accepted in some small shops; it was hit and miss in theatres and cinemas.
This was all in large cities. The situation was completely different in smaller towns and villages, where almost no shops I visited accepted them.
So, to summarize, if you do mostly touristy things, you're fine with a card; cash is still the king otherwise.
Note that Visa and Mastercard are generally accepted in places that took credit cards; as are some local cards, too. American Express was only accepted in a small number of places (large hotels, airline tickets and a handful of other places). I didn't see any places that would accept Diner's card, Discover or any of the European ones.
In a restaurant always double-check that they accept payments by card even if they have VISA/MC logo. The restaurant owners may decide to stop accepting card payments temporarily (for many reasons, not excluding tax avoidance).
Usually a waitress/waiter tells you in advance that "their POS terminal is not working". However, sometimes they forget to do that, and you may be left in awkward situation if you run out of cash.