I have so far not been hiking close to Berlin. However, I know to areas that might be worth a try:
The Spreewald and the Mecklenburger Seenplatte. Also I just learned about the "Märkische Schweiz", a small low mountain range. I have never heard of the 66 lakes trail, so I can´t give you information on that.
Note that you can reach the baltic sea in about three hours, maybe that´s something you would like?
During my research, I was quite surprised how scarce information is in English (I am german). However, at most tourist bureaus people should be able to speak it, so phoning or mailing them is a good idea. You can try that directly in Berlin or at the suggested places (links follow). If you already know, where you want to hike (the 66 lakes trail e.g.), you can ask them directly for places to sleep.
Berlin itself is a big city with some nice places for short walks, but nothing I would call hiking. Around it lies the state of Brandenburg. It is mostly flat, has few forests and a lot of agriculture. Due to this, cycling and paddling (where possible) are more popular, hence my question if you consider that.
Despite this, there are two major long distance trails passing by: the E10 and the E11. Here you can find general information on the E-trails and here on their particular way in Brandenburg (in German, sorry).
Very beautiful lowland forest. Most people go here to kayak along the small streams and channels in the Spree. There are cycling trails as well as dayhikes. The E10 crosses here (Werben till Groß Köris would be the etaps), so there should be a marked long distance trail. If I would be to hike near Berlin, I would give this a try because it is by far the nicest nature in this area. There are a lot of small villages and, during summer, tourists and it is far from wild. There are a lot of places where to sleep, it can be a little expensive though.
Here is their tourist information - all German, but you should be able to contact them directly. If you are also interested in history/culture, I would definitely give it a shot, since it is one of the few areas in Germany where there has been preserved some kind of folklore.
Get here: ~ 1.5 hrs to Lübben or Märkisch Buchholz by train, about 50-80kms.
An area with a lot of lakes: Made for paddling and cycling. However, the E10 passes by, so there should be some hiking possible ( I just read that it hasn´t been realized yet between Strasen and Stralsund, which would contain the part through the Seenplatte. This information might be outdated, but please check with the tourist bureau! ). It would be a good idea to get in touch with their local tourist information, since there are some less densely inhabitated areas where its nicer to walk. They also provide some information in, well, lets call it "semi-english" on their homepage.
Get here: ~1.5 hrs to Neustrelitz by train
A nature reserve with a lush forest, some rolling hills and lakes. For information here (again, in German - sorry!). The E11 seems to pass it. You can probably ask also in Berlin about it.
This is a description of the latest "Berlin Hikers" day hike in this area.
Get here: ~1 hr by train (switching to a bus brings you closer to the forest, but you can walk through fields instead)
Hope you find this information helpful - maybe you could give a small update about your choice and experience afterwards?
EDIT3: Some small improvements for the "Märkische Schweiz" area (Eyal)
EDIT2: After @bashophils suggestion I will add the Saxon Switzerland and steal his links.
The Saxon Switzerland is a low mountain range very popular for rock climbing due to the large amount of cliffs. In my personal opinion it is one of the most beautiful places in Germany. A big part of it is a national park. Two options for hiking there would be:
- Following the Malerweg, a 8-9 day round trip. You can easily pick only a part of it, I specially can recommend etaps 2-5, but I don´t know the last ones. You have to pay attention where to sleep, though.
- Getting a room in the area, e.g. in Bad Schandau, and do a couple of dayhikes from there.
Both possibilities will surely provide a unique experience. I didn´t mention this area at first, because it is rather far away and doesn´t belong to the Berlin region. Also, it really merits a visit on its own (like the nearby state capital of Dresden).
Get here: ~ 3(fast train) hrs /4.5(slow=cheaper train) hrs from Berlin to the start of the Malerweg or to Bad Schandau in the heart of the area.
EDIT1: I just realized I should probably mention that all this is not about "untouched nature" but more or less cultivated lands. I would not call this suggestions a place for an outdoor experience, but more for a couple of nice dayhikes since you will have to sleep inside. Nevertheless, it can be beautiful, just don´t expect wilderness.