Interesting question!

Bank robbery actually wasn't even a federal crime until 1934 -- until then, it had largely been handled as a state matter, so criminals could theoretically skip town and "get away with it" without too much trouble, since they would be outside the jurisdiction of local police. Of course, people who kept robbing banks tended to end up shot or hanged eventually, and most of the best-known bank robbers are the ones who died in a glorious shootout with the local police, because those stories make for the best movies (and because the successful ones generally had the good sense to keep quiet).

Up through the 1920s, the FBI (which was not yet called the FBI, it was still just the "Bureau of Investigation") had pretty much bungled its way through existence. Case in point: the Palmer Raids, which were intended to round up politically subversive types during World War I and which did not go very well. It didn't much help that Woodrow Wilson was preoccupied with the matter of the war, and Warren Harding appointed an Attorney General who had more in the way of personal loyalty than he did personal integrity. Oh, and trying to cover up Harding's many political scandals really didn't help. Things eventually started looking up, though, and eventually the United States found itself with Homer Cummings leading the Justice Department as Franklin Roosevelt came into office. His influence can be seen in making the FBI what it is today.

Now, at the time, the soon-to-be-renamed Federal Bureau of Investigation was not responsible for a large number of crimes. Mail fraud, bank fraud, violations of the Mann Act (transporting women across state lines for "immoral purposes") and the Dyer Act (car theft) -- that was basically it. Then, the country was rocked by a scandalous, high-profile crime: the kidnapping of Charles Lindbergh's son, which resulted in the death of the baby and the execution of a man whom a growing body of skeptics believe was wrongly convicted. (But I digress.) In the aftermath, Cummings was able to get the 1932 Federal Kidnapping Act introduced and passed through Congress, which made kidnapping a federal offense and thus gave the FBI jurisdiction to investigate this crime, a responsibility which they continue to hold today. Then Cummings turned his attentions to bank robbery, because wow, American banks were really not doing well in the 1930s for some reason, and getting pillaged by outlaws repeatedly was really not making things better.

While FDR was running through laws to protect money in banks and restore public trust in the institution (see: Glass-Steagall), Cummings was focusing on the criminal consequences of robbing them. Prohibition ended on December 5, 1933, but by this point the people and organizations which had made money dealing in alcohol were well-entrenched enough to simply switch professions. And what better way to earn a quick buck than by robbing a bank or twelve?

Anyways, the modern FBI sprung into being after a bit of bureaucratic reshuffling, and by the time it was done they had a new responsibility: investigating bank robbery. The Federal Bank Robbery Act, introduced and passed in 1934, made it a federal crime to rob any national bank or member bank of the Federal Reserve System. This was extended in 1935 to also cover banks insured by the Federal Deposit Insurance Corporation, which was basically all of them. Within a year of the Federal Bank Robbery Act's passage, J. Edgar Hoover could boast to his superiors that eighty bank robbers were now sitting in prison, and that losses to bank robbery had gone down a reported 84%.

Up until this point, affairs were basically as John Mulaney described. State and local law enforcement officials were hampered by lack of cross-border jurisdiction, and in many cases incompetence and outright corruption. Men like John Dillinger became nascent celebrities, and kept evading prosecution for their crimes. Once the Federal Bureau of Investigation hit the scene, things...got better, more or less. This isn't to say that J. Edgar Hoover was a frickin' wizard, but having a national organization with federal resources and the ability to coordinate with people in multiple counties or states really helped out. There is a reason that large criminal gangs that carry out the sort of open bank robberies previously common are now basically extinct. Organized crime today tends more towards selling contraband and more low-visibility activities.

The vast majority of information contained here came either from the public-facing History pages of the FBI's website or from the book A History of Heists: Bank Robbery in America by Jerry Clark (a retired FBI agent) and Ed Palattella (a journalist). The book's an easy-reading but informative text (and by its authors, I presume it's reliable on its subject matter); I highly recommend it.

Follow-up: How much of the 1920s/1930s crime wave was connected to Prohibition?