Essentially the galaxies will merge together to form a single elliptical galaxy (both are currently barred spirals). Using images of other colliding galaxies and computer simulations, astronomers have laid out a series of steps for a head-on collision between the Milky Way and Andromeda.
Phase 1: The Andromeda galaxy appears simply as a spindle-shaped smudge of light in the northern autumn sky. Because it is 2.2 million light-years away – or roughly 20 times the diameter of our Milky Way galaxy – it only appears four times the width of the full moon. As the two galaxies approach each other, Andromeda will grow ever larger in the sky, resembling an eerie glowing sword of light.
Phase 2: When the Andromeda galaxy and our Milky Way galaxy are close enough, huge clumps of cold, giant molecular clouds, each measuring tens to hundreds of light-years across, will be compressed. Like plugging in a string of Christmas light bulbs, these dark knots will light up as millions of stars burst into life. Most of these stars will be in brilliant blue clusters, many of them 100 times brighter than the original globular star clusters already present in the two galaxies.
Phase 3: The disk of dust and stars that for billions of years marked the lanes of our galaxy and the Andromeda galaxy, will also begin to come apart under the gravitational pull of the two galaxies. As Andromeda swings past our galaxy, the sky will grow increasingly jumbled with tattered lanes of dust, gas, and brilliant young stars and star clusters.
So many new stars will be born that the fraction of massive stars that are present will increase dramatically. These stars will begin popping off like a string of firecrackers as they self-destruct as supernovae.
Phase 4: After swinging by our galaxy, Andromeda will take perhaps 100 million years to make a slow and graceful U-turn, before plunging nearly directly into the Milky Way's core. Another, even more spectacular burst of star formation will then occur, with the winds from the supernovae driving most of the remaining gas and dust out of the galaxy. Soon both the old and new stars of the two galaxies will intermingle to form a single elliptical-shaped galaxy.
Phase 5: As the stars gravitationally settle into their new home, through a dynamic process called "violent relaxation", any hint of the Milky Way and Andromeda as majestic spiral galaxies will be gone. The band known as the Milky Way will be gone, but far in the future some astronomers might gaze out onto a starry sky and look all the way into the core of the new elliptical galaxy. They would have no clue that there were once two majestic spiral galaxies, called the Milky Way and Andromeda by a long forgotten civilization.
All of this will take billions of years as the galaxies repeatedly come together and then separate. The distances between stars are so great that few will actually collide, but the constellations will be scrambled and the night sky completely changed from the current state. Also, new research suggests that the collision has already started, despite the main parts of the galaxies being roughly 2.5 million light-years apart. This is because regions called the galactic halo of each galaxy may be overlapping. The halo is a sparsely filled (even by space standards) portion of the galaxy which extends far outside of the main body.