I don't have a direct source for most of this, so it could be made up, but I had a friend who used to live in this area who was a Pagan. I don't mean a neo-Pagan or a 20th (or 21st) century Wiccan. I mean he was really into the old ways and studied up on them. I asked him about this and he said that it was originally ceremonial. There was a ceremony Pagans would use for cleansing the ground and marking it off to keep evil spirits out, and this involved hold the broom between their legs, which would look like they were riding it, and walking and kind of hopping around the area they were cleansing, basically defining a perimeter to their "clean" ground.
There's a good chance that it was only the women who did the hopping with the broom between their legs, since it's a phallic symbol, and it may have also been a fertility ritual, so the ritual very likely had a sexual/reproductive element to it. (Especially since the idea was to make the ground ready for crops and planting.)
I wish I could state this authoritatively, but I only have his word to go on. I will say that he really got into researching the "old ways" and being able to "educate" modern Pagans and to show some of them that they really knew very little of the traditions he had been studying.
This also comes close to what the article on flying ointment says when it mentions that "It was said that witches were able to fly to the Sabbath on their brooms with help of the ointment." But it also goes on to say, "Likely the riding of the broom has a different origin."
Since you're referencing Harry Potter, I'll include the explanation from that universe as well:
According to the Harry Potter wiki, the earlier magickers (I'm tired of typing out witches and wizards) did not know of spells to make themselves fly, but they could make objects fly. According to the article on brooms, they could make objects fly, but not humans.
The problem was, that even then, they knew muggles would be jealous of their abilities and that it was best not to let them know of the ability to fly. That meant whatever object they used to fly needed to be something that could be kept in their house, that was easily accessible, but that would look completely innocent to visitors.
And a broomstick was one of the few items that would be present in every house, that had a reason for being in the house, and could be ridden on (even if it wasn't comfortable).
So magickers found it easy to just use brooms for flight.