As a first, informal approximation, one may think andarsene as a kind of “phrasal verb”, composed of a “normal” verb (andare) and some suitable particles (in this case, a personal pronoun followed by ne). So, while andare simply means “to go”, andarsene means “to go away”. Hence, as one comment mentions, the sentence Non se ne devono andare tutti? means “Shouldn't they all go away?”.
In some forms of the verb (infinitive, gerund) the particles are often kept in a single word at the end of the verb itself: andarsene, andandosene. In most forms (indicative, subjunctive, conditional) they are split from it and occur before it (but together; one cannot split the se from the ne): ce ne andiamo, te ne andresti.
As these examples show, you don't actually always use se, but rather the personal pronoun agreeing with the subject: io me ne vado (first person singular), tu te ne vai (second person singular), lui se ne va (third person singular) and so on.
Finally, this se is indeed not that same se that means “if”, but it's not “si + ne”. Ne is a separate pronoun that happens to also appear in this verb. Se is a variant of reflexive pronoun si (“Gianni si mette il cappello”) which is used in certain positions, especially before another pronoun (“Gianni se lo toglie”), as here. See here.
More technically, these verbs are in a category called verbi pronominali; see here for more.