Marx was born in Trier - part of Prussia - in 1818. Prussia was a founding state of the Confederation of Germany. The Confederation of Germany was created at the Congress of Vienna 1814-15 following the fall of Napoleon. Marx was born a German!
He was expelled from Prussia in 1849. Was he then stateless (a citizen of the world)? Probably yes if you project back our modern legal conceptions (underpinned by international laws adopted in the 20th century) of what comprises citizenship of a state. But you don't want to project back our modern understanding of 'Germany' and 'German' because the unified state didn't appear until 1871!
NYVBlue is right that most people who throw around the term 'Marxist' have no idea what they're talking about.