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 was 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 equals 2/3 centimeters or 0.26 inches.
People get used to it, and now it's the sizes of shoes. I.e., 42nd size equal to 42 Paris points.
This system was adopted in Europe and Russia, but the UK went its own way. They've decided to use barleycorn - an old English unit of length - the barleycorn's average size. It was equal to 1/3 inches or 8.46 millimeters.
But that's wasn't enough; 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 were 13.5 sizes for children and then were adults sizes which started from 3rd.
Americans have gone even further. They've changed the minimum practical length and added men and women sizes. For the kids, the sizes start from the minimum of 11.67, from 24 for men and 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 9, 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 shoe size is the size of 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 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 is 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.