borders & labels for zipcode and federal state

I am absolute new to OSM and all the tools and file formats around it.

I need a map with the borders (incl. labels) of German federal states (Bundesländer) and the zipcode (Postleitzahl). There are zipcode areas not fitting the borders of federal states. I need to check some borders with my eyes about that.

I use QGIS 2.18.28 from Debian 10 64bit repository and found this tutorial for QGIS which I where able to draw and label the zipcode areas.

The federal state borders are still missing in the map.
Now I am not sure what I need next in technical terms. What do I have to search for? Are borders in a shape file?
Do I need a “shapefile Bundesländer” or something like that and then just drag and drop it into the layer area of QGIS?

Or am I totally wrong here?