As you might expect, it comes from the boxing ring (well, we supposed that some of you might have guessed the circus ring...). In the early 19th century, when boxing was quite popular, one who wished to challenge a boxer would throw his hat into the ring. This was probably necessitated by the crowds and noise at such events; you'd be missed if you simply tried to shout out a challenge or push your way through the crowd and into the ring. John Hamilton Reynolds wrote in The Fancy: "Throw in his hat, and with a spring get gallantly within the ring." This is from 1820 and is the first recorded use of the term.
The phrase soon came to be used figuratively to mean "to enter a contest" and then "to enter a political contest". Theodore "Teddy" Roosevelt used it in 1912:"My hat's in the ring", he said, meaning that he had entered the presidential race.