...Or does this question not make sense because of Relativity?
Andromeda and the Milky Way belong to a group of galaxies called the Local Group. The two galaxies are the largest galaxies in the group, so to a pretty good approximation their interaction can be treated as a two body problem, with the other galaxies in the group producing only minor perturbations to their motion.
So as you suspected, it isn't the case that we are moving towards Andromeda or Andromeda is moving towards us. Both galaxies are moving towards their mutual centre of mass, which is somewhere on the line joining the two galaxies.
If you go by visible matter then Andromeda is about four times heavier than the Milky Way, but as BillOer mentions some studies have suggested that including dark matter reduces the difference and may even make the Milky Way heavier than Andromeda. Whatever the case, it seems clear that neither galaxy is so much heavier than the other that it dominates the motion.
As Bob mentions, the Local Group as a whole is moving relative to the cosmic microwave background, and the average speed of the group is around 630km/sec. The relative speed of the Milky Way and Andromeda is about 125km/sec, so it's small compared to the overall speed of the Local Group.
Their mutual gravity will pull them towards each other, with the more massive galaxy causing more acceleration on the smaller. According to this article the more massive is the Milky Way, so it will cause Andromeda to accelerate more than the Milky Way, not that it really matters. Since interstellar space is mostly empty (i.e. there is a lot of distance between stars), other than possibly being ejected from the combined galaxy, very few will be affected.
Strictly speaking, the universe has no rest frame (that we know of). If you want to set the rest frame of the CMB to be stationary, (which is reasonable in many applications), you may compare the velocity of the Milky Way and the velocity of Andromeda with respect to the CMB rest frame. (I don't know if anyone has ever done this, however.)
The CMB dipole should consist of two factors: the dipole due to our peculiar velocity (our motion through space) and a primordial dipole. However, there two would be near impossible to disentangle from each other, and as far as I know, nobody even considers this as an answerable question (at least among the CMB people I know).