I've recently contacted the DFS (Deutsche Flugsicherung GmbH) requesting information about launching a HAB, and what they returned me was a bit scary.
By §1 Abs.2 of the Luftverkehrsgesetzes (LuftVG) a “Freiballon” is an aircraft. Further, according to Luftverkehrsordnung §16a, a Balloon, that occupies controlled airspace (which starts roughly 300 meter above ground) must get an Airtraffic-control-clearance, if the combined mass of the payload and balloon (excluding gas) exceeds 500 gramms.
So, if you want to launch your balloon, you need to get clearance from the DFS by sending them a request. The request must contain the date of the launch, the exact position from where you launch, and the time at which you want to launch. Additionally, even though it's not required, it is encouraged to also tell them the length, color, weight, ascend and descent rates, aswell as the height ceiling of the balloon. It is very important that you send in this request 2 weeks before the launch, or it won't be accepted! I recommend sending it in 4 weeks earlier, to show them good faith.
You can send them the request via email to: firstname.lastname@example.org (they also speak english!)
When they accept your request, they will publish a NOTAM for you.
You should also make sure that you're not launching in the vicinity of a big airport or restricted airspaces. You can view an ICAO map depicting all airspaces in germany here: www.vfr-bulletin.de/web20/index.htm (You will have to select ICAO in the dropdown menu in the top right corner)
And now comes the part, that is really annoying: You need insurance for the flight to be legal. The Luftverkehrszulassungsordnung (LuftVZO) dictates, that the so called pilot in command has to have a liability insurance (Haftpflichtversicherung). You will have to contact your insurer and inform yourself about if and how you get insured. In case they don't want to insure the flight, you'll usually get redirected to another insurance company willing to insure you.
DO NOT FLY WITHOUT INSURANCE! I can't empathize this enough. It is very likely that nothing will happen, but IF something happens, for example your balloon causes a car crash with injuries and a wrecked car, you will be held liable and have to pay for the damages yourself. It also is illegal to fly without insurance, so you can also face criminal prosecutions.
http://www.dfs.de/dfs/internet_2008/module/luftsport_und_freizeit/deutsch/luftsport_und_freizeit/sonstige_aktivitaeten/index.html The DFS has this handy little page here with phone numbers and email adresses. Keep in mind that the information here might be outdated and you should contact the DFS if something isn't clear.