Although Berlin has more of a reputation, I'd recommend to also consider other places within Germany. Berlin, while having a lot of startups, is not the center of the "real" software industry. I recommend taking a serious look at companies in the Rhein-Main-Neckar region. This region has a cluster of big software firms, such as SAP, SoftwareAG and the companies working on software for the financial industry (Frankfurt), as well as Technical Universities (these are the ones that produce CS graduates).
Be warned, however, that you won't find anything comparable to SV in Germany. And I have to admit that there is also a problem regarding startups: The largest cluster of startups is in Berlin, but most of the money in the software biz is in West Germany. Btw, please don't get scammed by the Samwers.
Experience is definitely a plus, but probably more with the more "traditional" software companies than with the startups. Many German startups live off fresh degrees and high hopes (in the sense that they are founded by people out of the University), with all the positive and negative side-effects that this brings.
With regards to language, I'd say English and a willingness to learn German should suffice. Most of the software people already know enough English to work with them, and some corporations that operate internationally even mandate some degree of English usage. A few more rules of thumb: If the company is big or works in an innovative field, English should be all you need. If, on the other hand, it is located in a rural place or in East Germany, there might be problems.
These are of course generalizations. In any case, learning German will be helpful, even if it is only to facilitate the interactions with your surroundings outside work.