From Quidditch Through the Ages:
No spell yet devised enables wizards to fly unaided in
human form. Those few Animagi who transform
into winged creatures may enjoy flight, but they are a
rarity. The witch or wizard who finds him- or herself
transfigured into a bat may take to the air, but, having a
bat’s brain, they are sure to forget where they want to go
the moment they take flight. Levitation is commonplace,
but our ancestors were not content with hovering five feet
from the ground. They wanted more. They wanted to fly
like birds, but without the inconvenience of growing
feathers.
We are so accustomed these days to the fact that every
wizarding household in Britain owns at least one flying
broomstick that we rarely stop to ask ourselves why.
Quidditch Through the Ages - Page 1 - Scholastic Edition
I'm going to throw out a guess that Hagrid flew to the island on a broom, based on the above information, stashed the broom in his magical moleskin coat, and took Harry back to London via the small rowboat the Dursleys and Harry had used to get to the island.
Yes, Voldemort can fly; aside from Dumbledore, Voldemort is the most powerful wizard alive and, as Hagrid points out, doesn't have much human left in him. Perhaps this is what enables him to fly. Snape flies in Deathly Hallows, but was also a very powerful wizard.
As for using the pink umbrella ala Mary Poppins, I think it's a cute idea, but is it realistic? Hagrid's wand was snapped in half during his third year, when he was expelled. We all know from Ron in Chamber of Secrets how well (not) a Spell-o-taped wand works, and the wandlore in Deathly Hallows indicates that broken wands cannot be fixed (so says Ollivander). Harry is only able to fix his holly/Phoenix wand using the Elder Wand, which he is master of. We all know that the remnants of Hagrid's wand are in his pink umbrella; his wand seems to work for him for simple spells, but I don't conclude that it's a very powerful wand in general, and I don't think it would be strong or stable enough to enable Hagrid to fly. Especially since there are no known spells enabling witches or wizards to fly unaided.
I err on the side of a broom. It's a flying object that can be transported back from the island in Hagrid's magical coat of awesomeness! Hagrid would never abandon an animal -- a Thestral -- alone on a rocky island in a storm; creatures mean too much to him. And I don't think he would have left Sirius's motorbike on the island unattended and open to the elements. So, for me, it's a broom.
ETA: 05.02.12 I found something interesting at Pottermore in the section about Vernon and Petunia Dursley. JKR talks about witches and wizards being able to "go across water," almost as if she's implying they can somehow walk across water.
Even though Petunia was raised alongside a witch, she is remarkably ignorant about magic. She and Vernon share a confused idea that they will somehow be able to squash the magic out of Harry, and in an attempt to throw off the letters that arrive from Hogwarts on Harry's eleventh birthday, she and Vernon fall back on the old superstition that witches cannot cross water. As she had frequently seen Lily jump streams and run across stepping stones in their childhood, she ought not to have been surprised when Hagrid had no difficulty making his way over the stormy sea to the hut on the rock.
[J.K. ROWLING - POTTERMORE - VERNON AND PETUNIA DURSLEY]
This is still unclear as to how Hagrid actually crossed the water, but I think it definitely rules out a broom. So I was totally wrong on that. However, it does confirm that Hagrid had enough magical ability to cross the stormy sea, either by leaping the full distance (I don't think we know how far out to sea the Dursleys and Harry are when Hagrid arrives) or going from rock to rock across the sea. Anyhow, it seems as if Hagrid was able to cross the water using only magic; I know it's still ambiguous, but it doesn't seem, in the context of JKR's words, that Hagrid used any devices (broom; Mary Poppins umbrella; boat) or transportation magic (portkey; Apparition; Floo), and as he was at that point trained in magic only to the third year level, I can't help but wonder if the magic he needed and used to cross the sea was just basic inherent magical skills. It's still not totally clear, but I think we're able to rule things out with this information.