I think there's many levels of "theme" or "flavour" and Magic succeeds and fails at them to various degrees.
The one which I think is the most important is also the one Magic does best, which is what anotak points out - evocative cards that make sense in such a way that the theming of the card helps you interpret and remember its mechanical effect. It seems like most people think that this is limited to complex "top-down design" cards like
Endless Ranks of the Dead, but it's equally true for simple cards like
Fireball or
Lightning Bolt. In my opinion Magic is at its weakest when it falls down on this, and it seems like supplemental sets like Commander are the worst for this (
Sidar Kondo of Jamuraap is my personal bugbear in this regard, nothing about that card makes sense to me)
Then you have the setting, which I don't find especially compelling most of the time but occasionally there's something really cool. Ravnica and Innistrad are both interesting planes and the setting is reflected very well in the mechanics of the cards. This is also what I think a lot of people go to when they are discussing theme, even though in my opinion it's quite a minor part of theming.
Kind of linked to setting is characters within the setting. This is something that is sometimes done well and sometimes done poorly - recently the focus has been on the Gatewatch characters and I don't find them compelling at all, and to compound the issue they've been made the face of the game so cards which feature them tend to be very pushed, leading to Standard formats dominated by a few very powerful planeswalkers (or sometimes creatures) -
Gideon, Ally of Zendikar being the most egregious recent example. I prefer the approach they had of featuring characters in flavour text or in art so that they built up a sense of character, rather than doing it via a card. Jaya Ballard is infinitely more interesting as the sassy fire mage featured on Inferno or Incinerate that she was as
Jaya Ballard or
Jaya Ballard, Task Mage, simply because it's hard to fit a complete sense of character into just one card.
Finally, the plot of Magic, which is by far the weakest part of it. I have read some of the story articles on Wizards and I did even try and read the Future Sight novel, as I got it for free in with a purchase of some cards, and managed about three pages before I stopped. The problem is that a trading card game is not a good way to tell a story, as your readers will all open and read the cards in different orders and try and decipher what are important plot cards and what are not. The only time I think they've pulled this off with any degree of success was Khans block, which told its story mechanically very well through the block structure. The best story card of all time is
Crux of Fate, although its competition is somewhat lacking.