I did my Ph.D. from Germany where I received a tax-free fellowship, and now I got a postdoc offer in Bremen with salary range TVL-13. The 'Stufe' depends on the previous experience of the employee, but since I was not paying tax and was on a student visa during my Ph.D., will my previous research experience count in this case? Would be great if somebody could answer. Thanks.
In general, no. The previous work experience you can claim for a higher entry point on the scale needs to be relevant for the job for which you are applying. There are very general rules about this (since the TV-L covers everything from dishwashers to head physicians) so there is some leeway in interpretation, but the basic assumption is that the duties of a postdoc are different enough from those of a PhD student that experience as the latter does not count for the former. Time in education (which a PhD counts as) are also explicitly excluded by the regulation.
It might be possible to claim that even as a PhD student, you already performed duties of a postdoc (independently organizing tutorial sessions for a large class, say, or managing the IT needs of your department), but the usual case for a higher entry point is if you previously were on a fixed-term contract of, say, five years where you received your PhD after year four. Then you could claim the last year as previous experience for a postdoc position at another university.
EDIT: See also my previous answer to a similar question. In short, you need to distinguish between times which must be counted by law (which your PhD experience definitely doesn't fall under) and times which may be counted if argued for specifically, e.g., with arguments as in my second paragraph.
The answer is a clear "it depends". For instance, the DFG has a document explaining this available here, where it is stated that this is decided on a case-by-case basis.
During the hiring process, there will be a form that you will have to fill out about your previous working experience. Feel free to list your PhD studies under a scholarship there as long as you don't make it appear like you were salaried. The decision whether it counts will be based on the information that you provide. If you can prove that the work you did was equivalent to salaried position (e.g., involving teaching and research, both with provable outcomes), this may work.
Bremen has the reputation for being a bit special, though, as they involve the "Personalrat" in many decisions during the hiring process, which most likely includes determining whether your previous experience counts, so the rules of thumb from other German universities should not be relevant for you.