I've often wondered where this expression came from. My affinity for things that make sense found this phrase revolting from the first time I heard it. I can think of some ways to try to make sense of them, but all of them end up seeming implausible, confused, or both.
It could mean what it literally says. Some difference is being calculated. The first might be 13-10 and the second 4-1. They're the same difference, since they're both 3. Is there some difference in common every time this phrase gets used? I doubt it. The difference people are referring to is the difference between the two things being compared, not some difference within each of the two things being compared.
So that leaves us trying to make sense of how the difference between A and B, which is not much of a difference, is then the same difference. The same as what? As itself? That's trivial. There is a difference between A and B, or there wouldn't need to be someone saying that they're somehow the same. Yet what's this difference the same as? If it's saying that they're the same and also not the same, then that might make some sense of this, but they would have to be the same in one sense and not the same in another sense for this to have any meaning at all and avoid contradiction. I don't think most utterers of 'same difference' are thinking on this level of things being the same in one sense and different in another.
Equally implausible as a matter of interpreting people, but probably most charitable, is the theory that people are saying that there's a difference between A and B, and there's a difference between B and A, and those differences are the same difference. I doubt that's what's going on, and still it's got the problem of not meaning fitting with the contexts of utterance. If this is the correct reading, then you could say 'same difference' with respect to some very different things. If I ask my son if he wants to read the dinosaur book or scratch his head, and he said 'same difference' in response, it would make no sense. (If he knew the phrase, this might happen, since he doesn't quite get the point of saying things in context.) Those aren't the same activity, and that seems to be what the expression has come to mean as it's normally used. It should only apply to really similar things.
So I think it's just a confusion. We say two things are the same if, in the relevant context, any differences aren't important. We'll say that it's the same situation or the same thing. Yet we also might say that there's no difference or that it makes no difference to us. These involve the same sort of meaning, and it might possibly happen that someone mixes them together, as with the awful 'irregardless', which confuses 'regardless' and 'irrespective' and then actually gives the opposite of the intended meaning. This is on the level of larger phrases instead of word compositionality, but it's the same phenomenon. I don't know if some sort of common error became more common through conscious imitation because it sounded cool, or if someone coined it at some point, thinking it was cool to say something literally meaningless whose intended speaker meaning could be detected initially from the context.
And for those who though that it was obviously a confusion from the start, who wonder why I went through all the above, well it's fun. I enjoy trying to find a literal meaning for something obviously some sort of figure of speech, and this confused and literally meaningless one gives all sorts of opportunities to do that.