"Se" in this case is the form "si" takes before pronouns, and it's there for a reflexive function (e.g. andarsi a prendere un caffè - to go get a coffee [for oneself]); "ne" is there as place adverb, meaning here or there. So "andarsene" is to take oneself out of a place, to move away, to leave a place; it's idiomatic, instead of "se ne va" it could have been "va via" (goes away, leaves).

I thought so too, but I thought maybe it's because I'm pretty new to the pronomial verbs.

I only got it because I saw the sentence at an earlier attempt in a different question type.