You vote on a proposal/bill/decision. There are two sides: the one side is for it, and the other one is against it. These four animals voted twice, on both sides.
Both chambers plan to vote on that policy before January 15th.
He faces a vote on his future at an annual meeting next week.
The committee voted on the proposal, and accepted it unanimously.
Now that we've heard all the arguments for and against the proposal, shall we vote on it?
Similarly, you decide on a matter, you express an option on a subject. In this sense, on means dealing with the subject of; about; concerning (15).
on the side
Speaking metaphorically, voting draws a line between the supporters and the opposers. When you vote, you position yourself on one side of that line. In this sense, on means "expressing figurative placement or attachment (3)" and is derived from its main physical meaning "positioned at or resting against the outer surface of; attached to (2)".