There's another related instructable: LED Floaties by tetranitrate. The floaties didn't get to float up up and away, but made a cool temporary art installation at a park!
Video of the construction and launch:
Step 1: LED Throwie minus magnet
There is also some maths you can do to make sure your balloons are going to fly:
The volume of a sphere:
V = 4/3(pi)r3
And we used 12" latex balloons, so r = 6 inches, which gives ~904 cubic inches or ~15 liters of helium per balloon.
You can approximate for every liter of helium used, you can get about 1 gram of lift, the battery and LED were about 4 grams, the balloon itself was around 3 grams and we can give another gram for the tape and URL paper. The payload for the helium was a total of ~8 grams, which is a ready for launch Houston!
Step 2: Stuff your balloons
The video in the intro has a good demonstration on how to do this, but basically just have someone stretch the neck of the balloon like it was a sock about to be put on and have another person insert the LED unit. Simple!
Step 3: Fill them up and bag 'em!
You can start bagging them for transport, we just used large black lawn bags, which held around 7-10 balloons each. In total we had about 70 balloons, including one large 24" with 5 LEDs on it!