The following text is based on Wikipedia
Here is a free paraphrase.
A long time ago, when there was no metric system (and it's still absent in some places), there were shoemakers who made custom shoes - they measured client's feet. Those who couldn't afford shoemakers made their shoes by themselves. Later there were a great Industrial Revolution and shoes started to be produced en masse. So, the shoe size system had to be introduced.
French, who were really smart guys (they invented the metric system), decided to use Paris point as a unit of length which is equal to 2/3 centimeters or 0.26 inches.
People get used to it and now it's the sizes of shoes. I.e. 42th size equal to 42 Paris points.
This system was adopted in the whole Europe and Russia, but The UK went their way. They've decided to use barleycorn - old English unit of length - the average size of the barley corn. It was equal to 1/3 inches or 8.46 millimeters.
But that's wasn't enough, in order to reduce numbers, they started the measurement not from zero as it was in Europe but from the minimum practical length - 12 barleycorn for kids and 25 for adults. There was 13.5 sizes for children and then were adults sizes which started from 3rd.
Americans have gone further, they've changed the minimum practical length and added men and women sizes. So for the kids the sizes start from the minimum of 11.67, from 24 for men and from 22.5 for women
As the gap between the sizes was too big (1/3 of an inch is much more than 2/3 of a centimeter) they decided to make shoes with half-sizes. For example, there was size 8, then size 8.5 and then size 8 and so on. The sizes are whole in Europe - 40,41,42.
You might think, how can I measure this size? Should I measure the foot or the length of the soles? No, the size of the shoe is a size the workpiece i.e. a wooden or plastic "foot" around which the shoe is sewn. It's considered that it's equal to the feet length plus 2 centimeters.
Here is a calculator that converts European size to UK and US below. It's for the convenience but it's better to try on your shoes.
P.S. Science doesn't stay in one place. The international standard ISO 9407 "System of measurement Mondopoint" was adopted in 1991. There, the shoe size is equal to the average length and width of the foot in millimeters. 280/110 for example. Because it's a progressive system it;s used by NATO and other military organizations.
P.P.S. Human care doesn't stay in one place too. There was a European standard EN 13402 for clothes sizes adopted in 2007. It's recommended to specify the shoe size in centimeters.