FAA

Before I start talking about who you need to notify about your launch I'm going to tell you that you should read Part 101 Subpart D of the FAA regulations. You can find the current version on the FAA's website. If you read the whole Part 101 regulation you'll notice at the very start that the regulation only applies to free balloons with payloads heavier than 4 pounds, so most amateur projects won't really fall under the scope of the regulation. You should still follow all of the rules in Subpart D to remove yourself from as much liability as possible. Not following the rules can lead to fines, imprisonment, and more importantly could seriously injure or kill someone.
Now, on to who you need to talk to. I have to admit that I've heard horror stories about dealing with the FAA and I was very nervous about calling. It doesn't help that I didn't really know what office I should call or who I needed to talk to about this project. I started by calling the FISDO (flight inspection safety district office) in Helena, MT. They seemed to be the most prominent FAA presence in Montana, and it turned out to be a pretty good choice. The FISDO doesn't have anything to do with small balloon launches, but they did point me to the right ATC (air traffic control) office. The ATC office doesn't actually have anything to do with small free balloons either, but information about your launch will get communicated to them through the NOTAM system. NOTAM (notice to airmen) is a system of hazardous condition reporting for the skies. It covers things from air shows to volcano eruptions...yes we're looking at you Iceland. The ATC office I talked to gave me a phone number for Prescott Flight Service Station (877-487-6867). They apparently handle all of the NOTAM reporting for the "West US." I have no idea what is included in "West US" so you should call the FAA ATC office closest to your launch and ask what the NOTAM reporting number is for your area. When you launch your balloon you should be ready to give your launch location, launch time, time to 60k feet ascending, time of reaching 60k feet descending, expected landing location, and expected landing time. You need to make this call no earlier than 24 hours before the flight and no later than 6 hours before the flight. If you cancel or change the times you need to update the NOTAM immediately. You should also notify the NOTAM station when you actually reach 60k feet up and down, if you lose communication with your balloon, and when your payload has landed if possible. That's all the reporting you need to do.
The 60k feet barrier is important because 99% of aircraft can't fly above that altitude. Unless you're hanging out in Korea or Russia there won't be too many U-2 spy planes cruising past your balloon and there's only one X-37 space plane in existence right now. So, once you're above 60k feet you can breath a little bit easier knowing that you won't be ingested by a jet engine. One note about launch site selection is that you need to make sure you are more than 5 miles away from any airport. It's also a good idea to plan your flight path so that it doesn't cross over any airports. This is in the Part 101 regulations, but it's easy to miss. My launch is still on for 3 JULY 2010 at 1 PM from the Billings, MT area (actual location to be selected about 4 days ahead of launch for weather reasons).