If we’re sufficiently patient, M31 is coming towards the Milky Way and should arrive in about 3 billion years or so. Intergalactic Travel is easy, given aeons.
However, if we’re talking mere megayears, then the trip to M31 and beyond requires boosting the transit speed. If we can accelerate at a continuous acceleration – undergoing so-called “hyperbolic motion” – then the ship-board time can be reduced to arbitrarily low values. With the proviso we can supply sufficient energy and protect ourselves from the high-energy photon/particle bath that cosmic-rays and the Cosmic Microwave Background both become. Aberration – the distortion apparent direction of objects moving towards the observer – means the incoming radiation becomes ever more restriction to dead-ahead, making mitigation somewhat easier.
Slower trips, at constant fractions of the speed of light, require the passengers/payload to remain in some kind of stasis, else the billennia will inexorably erode their viability. Alternatively a World-Ship is sent, sufficiently well provisioned to last several million years. Back in 1987 Burruss & Colwell proposed such a concept, with a vast 1,000 km wide World-Ship, 50 billion passengers, and a cruise speed of 0.4c. The antimatter fuel required would be the equivalent of several days worth of the Sun’s total luminosity, so it would require at least a Kardashev Type II Civilization dedicated to the task to achieve it.
A World-Ship or a whole World? What if we sent an Earth-mass planet, using tricky orbital maneuvering around the 4.2 million solar-mass black-hole in the Milky Way’s Core as our accelerator? A Type III Civilization, with control over the Galaxy’s resources, would surely be able to arrange such a minor rearrangement of masses in the Core, flinging the Intergalactic Planet-Ship outwards at 0.5c. But what would it require to stop in the target Galaxy?
Given the right materials a magnetic-sail might do the job. We can slow an Earth-Ship from 0.5c to 0.005c in about 550,000 years (11% of the trip-time) over a braking distance of about 36,000 light-years. The sail would be 13.4 AU in radius with a super-current of 68 giga-amps and a mass of about 15.4 quadrillion tonnes (if its density is about that of carbon nanotubes.) Thus immensely BIG and probably immensely strong. At the “wire” (1.5 metres in radius) the field strength is 9,240 tesla, which is about 100 times higher than the highest critical magnetic field strength of known super-conductors. Thus not material we presently possess.