Almost all stars are located in galaxies. When galaxies interact with each other, a very small number of stars may get lost and end up outside of a galaxy. However, because star formation requires relatively dense clouds of gas, which are only found in galaxies, the vast majority of stars are found in galaxies.
Until about 100 years ago, the Milky Way galaxy was thought to be only a few thousand light years across, and most thought it was the entire universe. Other galaxies had been discovered, but they were thought to be smaller objects within our galaxy.
The first galaxies were identified in the 17th Century by the French astronomer Charles Messier, although at the time he did not know what they were. Messier, who was a keen observer of comets, spotted a number of other fuzzy objects in the sky which he knew were not comets. Worried that other comet hunters might be similarly confused, he compiled a list to prevent their misidentification. Messier's list (where objects are identified by M for Messier, followed by a number, e.g. M51) contained information on 110 star clusters and “spiral nebulae” (galaxies) but it was almost 300 years before astronomers figured out what the fuzzy “spiral nebulae” actually were.
Some people argued that these nebulae were “island universes” - objects like our Milky Way galaxy, but external to it. Others disagreed, and thought that these spiral objects were clouds of gas within the Milky Way. The argument went on until the 1920s, when the American astronomer Edwin Hubble finally measured the distance to one of these spiral nebulae.
In 1923 Hubble was studying the Andromeda "Nebula" (now called the Andromeda Galaxy), when he realised that one of the objects he was observing was in fact a Cepheid variable star. Cepheids are stars whose brightness changes periodically over time, and they had been discovered by the American astronomer, Henrietta Leavitt, in the early 1900ʼs. Leavitt found what is now known as the Period-Luminosity (P-L) relationship, a link between the luminosity (brightness) of a Cepheid and its period. By measuring the period of a Cepheid (by observing itʼs brightness changes over several days or weeks), the P-L relationship can be used to determine itʼs actual brightness. Hubble used the P-L relation to find the distance to the Cepheid he was studying in M31, and proved that it was located outside of our own Galaxy. This finally ended the debate on the nature of the spiral nebulae – they were indeed distant galaxies like our Milky Way.
Hubble continued his study of galaxy distances, using Cepheids as his measuring tool, before publishing his results in 1929. In his paper, Hubble plotted a graph of the velocity of galaxies (obtained from determining the redshift of the spectra of these galaxies) against their distances (from Cepheid variabes). This plot showed that most galaxies are moving away (receding) from us, but also that the speed at which they are moving away (the recessional velocity) is proportional to their distance – distant galaxies recede faster than nearby ones. This became known as Hubbleʼs Law. Hubbleʼs initial estimates for the recessional velocity of galaxies was very high, because atthe time no-one knew that there were actually several different types of Cepheid variables, with slightly different Period-Luminosity relationships. However, recent advances in astronomy have now narrowed down the value of the slope of the graph (called “Hubbleʼs constant”), and results are converging to an accepted value of ~65 km/s/Mpc (i.e. galaxies recede by an extra 65 km/s for every Megaparsec they are away from us).