In the case of the egg, it contains mostly fresh water, along with some proteins that are denser than water, and some lipids that are less dense than water. As you add increasingly greater amounts of salt to the same volume of water, since the salt dissolves, you are increasing the mass of the liquid. Since the volume does not increase by the same amount, you end up increasing the density of the water as well. As soon as the density of the water is greater than that of the egg, the egg will start to rise. Even more interesting, you could get the egg to float in the brine, then pour in cooking oil. The oil is less dense than water, so it will float on the water, and the egg will float on the water, but be submerged in the oil.
If the salt water were not well mixed, you could even use the egg as a makeshift measurement device to test where the higher salinity water begins, since it will tend to sink in until it hits the heavily salted portion.