In the United States, these kinds of things are governed by FAR 101. It's reasonably straight forward to become exempt from _most_ of the rules by following the criteria outlined in section 101.1(4)[1].
Roughly, these regulations correspond to making sure that if a plane were to hit your unmanned balloon on the way up or on the way down that the plane will survive and that your package won't be dragged along; and, that the package itself won't be hazardous to folks on the ground.
(IANAL) Conformance with the rules means that no single payload is more than 6lbs, that the side-wall density of your payload does not exceed 3oz/sq in on the smallest side, and that the cabling you use will break with an impact force of 50lbs. We could debate about how you measure impact force, but most folks in this hobby read it to mean "tensile" strength. For 6lbs payloads, to meet the density requirement, you want a box about 1x1x1ft, which is often why most of the pictures of payloads that people send up in the sky look about the same size and shape.
Last, you need to conform with the safety regulations in FAR 101.7. The gist here is that you need to make sure that your payload isn't a danger to others on the ground, and not a danger to those in the air. Compliance here is more subjective, but a parachute and padding box go a long way to making others on the ground safe.
It's relatively easy to file a Notice To Airmen (NOTAM) that indicates you'll be launching a balloon. A courtesy call to your local Air Traffic Control office wouldn't hurt either. If you don't have a local ATC, the nearest airport is good place to start.
My familiarity with these regs comes from actually launching several helium-lifted payloads to near-space a few years ago and talking through the regs with the FAA and ATC to make sure we didn't need an official waiver (we didn't). My group had a slightly higher budget, but we went higher, longer and farther than these young Canadians, making two launches within an hour and sending the first balloon about 2000 miles over 34 hours starting at around 80,000ft, and sending the second balloon + payload to 123,000ft with about 3 hours of flight time.
Like many enthusiasts, our project used amateur radio frequencies to communicate, which qualified us to be listed on the Amateur High Altitude Radio Balloon (ARHAB) website for our achievements, we're listed as PBH-9 and PBH-10, for the duration and distance records.[2]
[1]:http://ecfr.gpoaccess.gov/cgi/t/text/text-idx?c=ecfr&rgn...
[2]:http://www.arhab.org/