Back in Kamigawa Block, Gifts Ungiven was a very popular card, showing up in a good percentage of blue decks. I don't understand why it's considered useful. What made this card so popular?
I'm sorry, you don't think that a Diabolic Tutor in blue (for the same cost) that tutors two cards instead of one (giving you card advantage), can be cast at instant speed (on your opponents turn with untapped mana that's a counterspell threat), and puts two cards in your graveyard is useful?
The only drawback is that the opponent gets to choose which two cards you tutor out of four possibilities. If they are all four good, useable cards, (which they naturally should be if you have crafted a good deck) this is hardly a drawback.
Many decks ran this with Psychatog, as those two cards in the graveyard and those two cards in your hand, if nothing else, help power the 'tog.
I've seen other decks run this with "return creature card from graveyard" spells. Gifts up two of these spells and two big beaters. What does the opponent do?
I found this article on Star City Games showing the sort of broken things you could do with Gifts in Kamigawa block.
Also, consider Careful Consideration
It costs the same (one blue mana instead of one colourless), doesn't let you choose which four cards to draw, and you only get to discard two cards if you cast it in your main phase.
Gifts Ungiven is a very undercosted powerful card with the potential to be broken.
The short version
Gifts Ungiven was — and is — popular because it's one of the most powerful and flexible tutor cards in Magic, thanks to its ability to find multiple relevant cards for just 4 mana, at instant speed. In practice, the card is much more powerful than it looks:
The long version
Gifts Ungiven isn't just any tutor card. Sure, it costs the same as Diabolic Tutor, with the following added bonuses:
So, it's at least as good as Mystical Teachings (also an instant-speed tutor with built-in card advantage — one that saw tournament play during Time Spiral Standard and later in Modern). But it's way better than that, too!
Gifts give you four cards. Not two cards, four cards — it's just that two of them will end up in your graveyard. And you get all those cards at the same time, which makes it an amazing combo tutor.
Your opponent gets to control which cards go where, but, with careful deck-building and skillful play, you can get much more power from the card by effectively removing your opponent's meaningful choices.
At the least, Gifts allows you to tutor for four cards and get the third and fourth best ones for the current situation into your hand. That's pretty powerful by itself, though it relies on building a deck that even has a third and fourth best card for many situations.
An easy way to get that effect is to run one-ofs of a bunch of very similar cards, so that your "third best" card is basically the same as your "best" card. Here's the classic example:
(I'm using general examples rather than all Kamigawa-block ones because it's much easier to think about what's good in general Magic than in the rather idiosyncratic world of any set's Block Constructed.)
Two of those cards will end up in your hand. Three of them are 4-drop sweepers. So, whatever your opponent picks, you're guaranteed at least one sweeper in your hand. (The fourth card could be anything, in this case — Path to Exile just fits because you can use it to answer a creature your opponent plays after the wrath.)
Running lots of functional equivalents takes up a lot of space in your deck. This isn't too bad for the sweepers example above, since decks often run three of four wraths anyway. When you've got one particular, functionally-unique card you really want, though, or a niche case where you'd only run a one-of.
A common solution is to run "Regrowth" effects, forcing your opponent to choose between the card you want and a card that'll fish it out of your graveyard.
An example from the Kamigawa era is Frank Karsten's 2005 Worlds (Standard) deck. Let's say Frank's opponent has an artifact that needs to be removed right away. The deck has one maindeck answer — Putrefy. Here's a way he could tutor it with Gifts:
Recollect gives you Putrefy back in hand. Reclaim can put it on top of your library; you could either cast Reclaim on your upkeep and draw the card naturally, or use the Top to bring the card to your hand. Your opponent can make you spend a couple of cards and some extra mana to cast Putrefy, but, short of graveyard hate, he can't keep you from casting it.
Card you just want in your graveyard anyway
Hopefully you saw that this is where we were going when I mentioned Snapcaster.
The graveyard is a very active zone in Magic. So much so that some cards are actually at their most powerful in the 'yard. Kenji Tsumura's 2005 Pro Tour Los Angeles (Extended) deck includes Darkblast and Life from the Loam, whose Dredge ability helps power up his Psychatogs; as well as Wonder, whose in-your-graveyard ability is more relevant than the creature itself.
Flashback cards are great to tutor up with Gifts — whether they go in your hand or the graveyard, you can cast 'em either way. In addition, it's important to note that this is a valid Gifts pile:
That's it! Just two cards.
(The "stated quality" in this case is "different names".)
Since your opponent must choose two cards to go in your graveyard, both of these will end up in your 'yard. At which point you can flashback Rites and bring out your big reanimated finisher. It's the best graveyard-filling tutor this side of Entomb!
I believe the first example of using Gifts like this was actually during Kamigawa block. During one of the Pro Tour matches, a player was about to lose the game but had Goryo's Vengeance and Gifts in hand. So he Gifts-ed for just Kokusho and used the sac trigger from Goryo's Vengeance to kill his opponent.
Combos and engines
You know how Tooth and Nail is so good because you can dig out both pieces of a combo at the same time?
Gifts does that as well. It's especially easy with graveyard-based engines. For example, Patrick Chapins' 2008 Pro Tour Berlin (Extended) deck could set up his win condition using something like this:
Regardless of which card goes where, this sets up an engine that lets you make a bunch of Worm tokens every turn.
Plain old deception
Setting up "no-win scenarios" for your opponent is powerful and consistent, but sometimes you don't even need to do that.
You show me this Gifts pile:
Now, I do have real, serious choices here.
There are right choices and wrong choices, but they're based on hidden information. If I guess wrong, you're probably won the game. You're taking a chance when you do this, of course, but it's a chance with a big upside.
Another common way to play mind games with your opponent is to use the Regrowth trick detailed above, but then regrow some other card that was already sitting innocuously in your graveyard.
Whatever cards your opponent chooses you'll get all parts to your soft lock. This is just an example, I'm sure there are a lot better card combinations to fetch for. Keep in mind this is for the reasonable cost of 4 mana instant.
To add to ghoppe's answer: Over the past years, MtG has become a very mature game. In particular, library and graveyard manipulation have become very popular, getting a lot of love by the designers, and many mechanics as well as cards now involve these zones.
Considering this, Gifts Ungiven is a very powerful card that, if you design your deck right, actually gives you up to four cards of your choice, two of them into your hand, and three (including Gifts) into your graveyard. Since it's an instant, you can play it at the end of your opponent's turn, which further increases its versatility.