What does friends with each other mean? Is it different from "friends"?
No. "With each other" is fairly redundant here, I would say. If the two people (or more than two) are present or it's clear who is being talked about then "We're friends" would suffice.