How does 'z' translate to 'of' and not 'with'? Does it change with the noun being in a different case?
"Z" = from/out of/made of/with (that's what English wiktionary says). This here could be treated as "out of", I guess - I'm talking about each and every one out of the group we are discussing.
But more importantly, very often the prepositions don't correspond at all between different languages. Things are just said in totally different ways. It's probably better to think in terms of whole constructions than translating prepositions, or at least you need to simply be careful with them.
How would you say: I am talking about everyone with them. In my example, "everyone" is not necessarily the same group of people as "them."
"Mówię o każdym/o wszystkich z nimi".
but I would probably change "mówię" to "rozmawiam", as 'with them' implies a conversation.
I have to correct the suggested English translation, as I was wrongly told I had an extra space. I did not. "Everyone of them" is wrong. It should be "every one of them".