Finding a place to live in Berlin is a strange little beast. It is both easier and harder than one might expect. It seems generally agreed that the three places you want to live are:
1. Kreuzberg
This is the "hippest" area of town. Perhaps the best nightlife scene if you are 32 or under. And not going to work in a suit. A lot of Turkish people live here - but more and more students and artists. I saw an apartment here that was 600m2 on two floors of a building occupied by 10 artists of various type. I felt that there was the most competition for places here - perhaps because of all the places I saw none were offered to me.
2. Friedrichshain
This, from what limited information I have gathered, seems to be kind of the new Prenzlauer Berg. Still kind of crappy, but getting the cool treatment now. I can't vouch for the nightlife personally but I hear that it is pretty good, and it is pretty easy to get to Kreuzberg if you are there anyway. I was told that the houses here are generally kind of crappier than in Prenzlauer Berg, but that if you are lucky you can get a really good one.
3. Prenzlauer Berg
Here, you have less of the feeling that you are going to "steal" a wicked place - like you might be able to in Friedrichshain or Kreuzberg, but every place that I saw seemed pretty decent. Prenzlauer Berg has kind of had its gentrification process already done on it, and to tell the truth, it makes things pretty damn convenient. I have every store/shop I need within a 3 minute walk of my house, and there are plenty of cool enough bars around, like Dr. Pong for example. I am living here, and it seems like kind of a nice and convenient place to stay while you look for some totally wicked steal in Kreuzberg or elsewhere.
3b. Mitte
It seems that a lot of people are a bit down on Mitte but that is mostly bullshit. It is, as the name implies, central to everything, and like in PB, there is easy access to all amenities. Which is nice. The price is a bit higher than in the other places though.
Some good websites for looking for rooms in shared apartments (that is what I was looking for) are:
http://www.studenten-wg.de
This is quite good. Clear layout, usually photos available. You can also get apartments for yourself here. But if you are looking to share a place, make sure you click on WGs when you start searching. WG is the keyword for "shared flat", it actually means Wohngemeinschaften (shared living arrangements).
http://berlin.craigslist.org/hhh/
Not great. Nice because a lot of stuff is in English, but the prices are generally kind of high. Sometimes you can find gems, and if you are just staying for a short time it can work out - especially since they are usually furnished. But, really it is not hard to find that on the german WG websites either.
http://www.wgcompany.de/
The layout on this website is weird and I found it really inconvenient the way they listed the apartments but I did find a few things that didn't seem to be listed anywhere else.
http://www.wg-gesucht.de
This one also has a really good layout. It shows you right on the search page how many girls/guys live there and has quite a bit of information in general. This one and the first one are probably your best bets.
You can also look in newspapers and stuff, but I didn't bother.
Everyone says Berlin is cheap and it is true. It seems that you can get a "decent" room (16-30m2) generally for somewhere between 230-350€, including utilities. Of course you can get insane deals. I have a friend who lives in Kreuzberg in an incredible apartment where he has two rooms for himself and pays a total of 150€. Nice. For him.
Things to keep in mind:
Kalt/Warmmiete
This means without/with utilities. Often the price given is "kalt", so keep it in mind that you may have to add quite a bit to the price. For example, I am paying 180€, and I will probably have to pay 70€ in water/electric/internet/etc. costs each month. Heating here generally costs alot.
Deposit
I had to pay 3 months rent as deposit, and this is not that unusual.
Painting
They have weird rules about painting apartments when you arrive/leave in Germany. This article on apartment rental in Germany explains it much better and also has a great section which explains a bunch of the abbreviations used in housing ads.
