Magnetotactic bacteria have a built-in compass, in the form of a magnetosome chain made up of magnetic biominerals, that allows them to passively align along terrestrial magnetic field lines. They also sense oxygen gradients and swim using at least one flagellum. Hence, these bacteria are self-propelled active matter capable of displaying flocking behavior. This Colloquium explains the physics behind these various capabilities, as well as their interactions and biological significance.