It is literal, but not a common expression or idiom. In English we would say "we having nothing in common", something like "we have no shared interests", or occasionally in cases of people who find it hard to communicate "we have no common ground" (to stand on/to start from). Now I have the song "Breakfast At Tiffany's" by Deep Blue Something stuck in my head.
As a native speaker, that was actually a suprisingly difficult question. I suppose that "gemeinsam" has a stronger focus on doing a thing together and simultaniously.
"Wir sind zusammen zur Schule gegangen" (We went to school together) -could be used even if you and the other person barely knew eachother and never really had a conversation. But "Wir sind gemeinsam zur schule gegangen" (Which I would also translate with "We went to school together") Implies that you and the other person referred to had some kind of relationship. Meaning you actually did something together not just simultaniously.
The "Gemeinsam" in the sentence above should on the other hand more thought of as in line with "die Gemeinsamkeit". Which is a noun for all of the things people have in common. You like apples? I like apples! Liking apples is our "Gemeinsamkeit".
You could try and think of it like this. Something we have in common is something we could enjoy together, something we could enjoy "gemeinsam", our "Gemeinsamkeit" I hope that made sense^^
If "Wir haben nichts" means "We have nothing", and "gemeinsam" means "together", why can this sentence not be translated, "Together we have nothing"?