Where can I find state borders for Germany?

You can download free state border layers of Germany from DIVA-GIS by selecting Administrative areas as the subject.

At http://www.geodatenzentrum.de/ you will find boundarys from the local community up to the national border.

Natural Earth is a great source for reference boundary data