Though the formation, and to some extent the evolution of galaxies still is one of the most active research areas in Astrophysics, some ideas are now widely accepted.
After the Big Bang the universe had a period when it was remarkably homogeneous, as can be observed in the Cosmic Background Radiation, the fluctuations of which are less than one part in one hundred thousand.
The questions of galaxy formation and evolution are How, from such a homogeneous universe, did we obtain the very inhomogeneous one we live in?, How did galaxies form?, How have galaxies changed in the past?
The most accepted view is that all the structure we observe today was formed as a consequence of the growing of primordial fluctuations by gravitational instability. Galaxies have formed in a "bottom up" process in which smaller units merge and form larger units. In our epoch, large concentrations of galaxies ("clusters") are still assembling.
There are some problems with this model. For example, recent data strongly suggests that the first galaxies formed as early as 600 million years after the big bang, hardly enough time for the tiny primordial instabilities to grow sufficiently. Also, spiral galaxies cannot be built up by mergers, since events as violent as a merger would completely mix up the fragile structure of the disk.
One way to escape the latter problem is the observation of High Velocity Clouds, clouds of neutral hydrogen that are still ``raining down on the Galaxy's disk. With some fiddling models can be constructed in which the bulge of spiral galaxies forms by mergers, whereas the disk can be regenerated by later infall of gas.
In the current universe, it is thought that large spiral galaxies such as M31 and our Milky Way are formed from numerous smaller galaxies being eaten by the larger galaxy. This is probably why M31's core is double. We can see this in action today in our own galaxy. The satellite galaxy SagDEG (Sagittarius Dwarf Elliptical Galaxy) is orbiting our galaxy at almost right angles to the disk of the galaxy. It's currently inside the disk, stars are being stripped off of it and joining the disk of our galaxy. Eventually, only the core of SagDEG will exist. Although it will have the same mass as a large globular cluster like Omega Centauri and G1, it will appear rather different, as it has far lower surface density due to the presence of substantial amounts of dark matter, while globular clusters appear, mysteriously, to contain very little dark matter. The Magellanic clouds will almost certainly share the same fate.
Giant ellipticals are formed in a similar way, but on a grander scale. The Milky Way and M31 are currently approaching each other at high speed. Eventually they will meet and pass through each other, gravity distorting both galaxies severely and ejecting gas, dust and stars into intergalactic space. They will travel apart, but not for long. They will again be drawn towards each other, and pass through each other. This will not happen for many times, eventually both galaxies will have merged completely, streams of gas and dust will be flying through the space near a newly formed giant elliptical galaxy. M31 will be thrown about the most by virtue of it's lower density and lower mass. Out of the gas ejected from the marger, new globular clusters and maybe even new dwarf galaxies may form and become the halo of the elliptical, as well as the globulars from both M31 and the Milky Way also being present, globulars being so tightly held together that they are largely immune to large scale galactic interactions. On the stellar scale, little will happen. Stars do not collide in galactic mergers since there is mostly empty space between stars, even in a cluster. If anybody is around to watch the merger, it will be pretty much an anticlimax, although the sight of a distorted M31 spanning the entire sky should be spectacular. M31 is actually already distorted - look at the edges of it, they're warped. This is because of interactions with M33, a face on spiral galaxy not far from M31. Eventually all three galaxies will be one giant elliptical galaxy, rushing to take it's place in the Virgo Supercluster.