When do you use dengan? Can one say Saya pergi dengan dia?
Yes, you can say "Saya pergi dengan dia".
It means the same.
It's an intransitive verb (without subject or object) meaning "being-together"
Not every verb requires a prefix. In the case of pergi it never takes a ber- or meng- prefix. It's just always on its own. The only derived forms that KBBI mentions are nouns kepergian (departure) and bepergian (travel)
Why is bersama also a ber- word? I don't see it falling into any pattern described in lesson tips.
"Together with" is redundant, and should only be used when the circumstance requires additional emphasis. For example, "Sorry Roni, I can't go with you in your car, because I'm already going together with them in their car." This additional emphasis strengthens the "togetherness," making it harder for Roni to convince me to go with her. Is this emphasis the intent of Duo Lingo?