During the 19th century and into the early 20th century, battleships were the Kings of the Sea, and every naval power of note had at least one. When did they lose this title to the aircraft carrier, and was it a particular battle, event, or was it a more gradual series of events that lead to the changeover in naval strategy?
I would date the transition to aircraft carrier domination to the Battle of Midway, in June 1942.
The Japanese fought an old style battle in four ship waves. In the first wave as a carrier task force, plus supporting cruisers and battleships, whose main task was to soften up Midway by air bombardment, and then screen the rest of the Japanese fleet.
In the second wave was a supporting force of four cruisers. In the third wave were the transports, escorted mainly by battleships and cruisers. And the fourth wave contained three of Japan's largest battleships, which was supposed to deliver the coup de grace to the American fleet, after it presumably rushed to save Midway.
After the destruction wrought at Pearl Harbor, the Americans had only one "wave," a carrier task force of three aircraft carriers and supporting cruisers, roughly equivalent in strength to Japan's first wave alone.
The battle degenerated into an air to ship battle, along lines similar to those of Coral Sea, fought a month earlier. With their greater focus, the Americans sank all four Japanese aircraft carriers, while the Japanese, who had been concentrating on Midway at the expense of watching out for American carriers, sank only one. (Two, if you count the temporary destruction of Midway as a "carrier.") The surviving American carriers then stayed out of sea range of the Japanese battleships, but the Japanese didn't dare to invade Midway while the Americans had carrier aircraft within air range.
This battle proved the dominance of carrier based aircraft over ships. Carriers had proven their worth at Coral Sea, but it was considered a "fluke" because no battleships had been involved. At Midway, Japanese battleships were present and had their "chance," but basically chose not to fight.
Sea power is not directly about which ship type can beat up which other ship type; it's a matter of being able to run one's merchant ships in an area and preventing the other side from running merchant ships.
In WWII, it was difficult for surface ships to protect a convoy from air attack, as we can see from the 1942 attempts to relieve the siege of Malta. Moreover, naval powers were hesitant to risk battleships in the face of enemy air power, particularly after the British lost a modern battleship and older battlecruiser to Japanese air attack off Malaya shortly after Pearl Harbor.
The questions, then, were whether aircraft carriers could defend themselves against battleship attack and whether aircraft carriers could protect shipping against battleships.
In WWII, carriers were generally able to not be sunk by battleships or other surface ships, unless badly handled like HMS Glorious off Norway. Their aircraft gave them warning of enemy forces, and their generally high speed enabled them to avoid combat. Therefore, they could stay in an area despite enemy battleship forces. (This was not always the case; in the 1930s, when carrier aircraft had much less range, US battleships "sank" US carriers a few times in the annual Fleet Problems.)
Their ability to defend shipping against battleships was a bit less certain. Normally, heavy air attacks would deter battleships from proceeding. After all, there weren't many battleships around, and they were expensive. If the enemy was determined to force his way through, some surface ships would likely make it through. This was shown by RN cruisers and destroyers around Crete and the Japanese Center Force in the Battle of Leyte Gulf, both of which carried out their missions despite serious losses. No naval power could afford to lose battleships with each mission, unless the enemy missions were extremely critical (the Battle of Leyte Gulf was an attempt to stop the first US landings in the Philippines).
Through the course of World War 2; in September 1939 battleships were still considered more important than aircraft carriers, and by VJ Day carriers were considered utterly decisive at sea. This process took a good few steps, however, and really examining it in detail could take an entire book.
You also need to consider the application of carrier air power to two main problems:
1) the decisive battle
2) the guerre de course, or convoy war.
So, first let's look at decisive battle. At the beginning of WW2, it was by no means taken as read that unsupported aircraft could sink a battleship; so while a carrier could do extremely well at finding a battleship, and keep a safe distance from her, sinking her was another matter. And the carrier could hardly replace the battleship if a carrier couldn't even sink a battleship. As a result, any would-be naval power had to have battleships in order to counter enemy battleships, whereas those who expected their navy to operate in range of land-based air support (Italian, German) did not need aircraft carriers. This assumption had to be overcome by experience, and there were several battles which made that example, and then rubbed it in the noses of the gun-deck admirals.
At Taranto in November 1940, the Royal Navy sank an Italian battleship in harbour and damaged two more, for the loss of two obsolescent torpedo bombers; so battleships were proven to be vulnerable to carriers when unable to manoeuvre freely.
In the chase of the Bismarck, the carrier aircraft did not sink Bismarck - however, they did damage her rudder, enabling her to be caught and destroyed by battleships.
Then we have the fate of Force Z - a surface-force only, consisting of a battleship, a battlecruiser and a few destroyers sunk by Japanese air attack. These were not carrier aircraft - the Japanese carrier force were somewhat busy at Pearl Harbor - but the crucial difference with Force Z, which differentiates it from Taranto and Pearl Harbor, is that Force Z was sunk while under sail, showing that any naval force which went into reach of enemy aircraft without its own air cover would be sunk.
Having already mentioned the parallel, I would be remiss to not cover Pearl Harbor - this is essentially Taranto writ large. It showed that if your enemy has a sufficiently powerful carrier arm, your fleet is not safe in harbour anywhere, not even across an ocean.
Then at Midway the combat between the American and Japanese carriers was decisive, without the Japanese battleships becoming engaged.
So, enough about decisive battle - what about the guerre de course, conducted primarily in WW2 by German U-boats?
Well, protecting a convoy against U-boats was helped hugely by air cover. Spotting the submarines in the first place, guiding in escorts to kill them or killing them directly, routing convoys around them (and providing excuses to use ULTRA intercepts to route convoys around them), forcing submarines to submerge and lose a chance to make an attack...the uses of aircraft in the Battle of the Atlantic were many and varied. However, at the start of the war there was a gap in the mid-Atlantic where land-based aircraft could not reach a convoy to protect it. Some desperate measures were used to help close the gap, including CAM ships (Catapult Aircraft Merchantmen which carried a single Hurricane on a catapult; this could be launched once, and at the end of the flight the pilot had to ditch the plane and bail out), the slightly more capable MACs (Merchant Aircraft Carrier) which carried about 80% of a normal cargo and had three or four aircraft embarked which could be recovered after a flight. These were stop gap solutions - as the war went on, they were gradually replaced with escort carriers, which were generally akin to MACs in that they were based on merchant hulls, with the difference that they were full conversions no longer carrying any cargo and could carry perhaps 20 aircraft - they were still too slow to operate with a fleet.
There were many aspects to the outcome of the Battle of the Atlantic, but unlike decisive battle where the battleship admirals resisted fiercely the supplanting of their beloved big-gun ships, the usefulness of air power to this aspect of naval warfare was little doubted, and the frantic attempts to close the Air Gap in the Atlantic show this quite clearly.
Battleships became obsolete with the rise of air power; this was clear to General Billy Mitchell at the end of WW I.
A 2,000 lb. bomb "near-miss" severely damages Ostfriesland at the stern hull plates (1921)
A series of tests were conducted between 1921 and 1925 which conclusively showed that battleships could be severely damaged or sunk by means of aerial bombing. It took time, and repetition, for the lessons to "sink in", but they did, and this lead to the creation of the air craft carriers which played such a prominent role in WW II.
The balance is found in "cost to build and operate" vs "cost to destroy"; air power is cheaper and more flexible than the battle ship. Note that coastal defenses in the form coastal artillery were also rendered obsolete by air power.
The Japanese sank the Royal Navies greatest and one of their most sophisticated Battle Ships HMS Prince of Wales and its older escort Cruiser HMS Repulse off the coast of Malaysia on 10th December 1941 using land based bombers and torpedo planes. The British ships had no air cover and were sunk relatively easily. These were the first ever capital ships sank purely using aircraft and the Allies realised a handful of torpedo planes sinking the Prince of Wales meant the era of the Battleship was over. Air power was everything and the Carrier was King.
See Z-Force mentioned in the answer above, Z-Force was HMS Prince of Wales and its escorts.
As other have said, the change became appreciated during WWII.
An important prerequisite for the change was the advent of aircraft engines in the 1000hp class, which meant that single-engine aircraft that could fit on carriers could also carry bombs and torpedoes powerful enough to be a serious danger to large warships.
Such engines started to come into service in the mid-1930s, which was only about one battleship building cycle before the outbreak of WWII. It's thus easy to see why the change wasn't appreciated until ships had been sunk.