This might lead one to wonder: if someone commits a crime (an
uncontroversial, completely non-political crime, e.g. old fashioned
theft or murder) in country A, then escapes to country B, who cannot
extradite him back to A, what typically happens next?
As another answer notes:
Countries can, and do, sometimes extradite accused criminals even in
the absence of an extradition treaty.
Usually, the first step is for law enforcement in the country where the crime was committed to discover the location of the suspect and contact officials in their own country's diplomatic service to have them request extradition from diplomats in the country where the suspect is located.
Do the two governments arrange an ad hoc extradition agreement, or
does country B's authorities deal with the criminal themselves, or
might he simply walk free? In the case of the second possibility,
how common is this? (I.e. is it common to prosecute someone for a
crime committed overseas?)
An ad doc extradition agreement wouldn't be uncommon. It would be very rare for country B's authorities to try or punish the criminal themselves for crimes committed abroad. It isn't that is has never happened, but it almost never does (incidentally, the same principle does not apply to civil lawsuits which usually can be tried where the defendant is found and resides or has a headquarters even if the underlying incident took place abroad; I've personally litigated such a case).
If the suspect is not extradited, that person would very rarely be prosecuted in country B, although the suspect might be deported if the suspect is not a citizen of country B and country B thinks that it is probable that the suspect committed a crime (this is what the U.S. would probably do if a non-citizen was suspected of having committed a serious crime abroad in a country to which did not want to extradite the individual, for example, due to a death penalty available in the place where the crime like drug possession was committed).
Customary international law, which not all countries (including the U.S., see Manuel Noriega) honor strictly, forbids extraterritorial prosecution for crimes that are not crimes under the territorial scope and criminal laws of the place that is prosecuting the crime.
An extraterritorial criminal prosecution would usually only take place for something like a war crime under a concept known as "universal jurisdiction" over crimes against all of humanity that is recognized in some countries. Another exception applies to crimes such as piracy committed on the high seas where no state has territorial criminal jurisdiction, which are often prosecuted by whomever captures the suspects in this "no man's land".
Ultimately, whether there would be an extradition depends upon the country in question ("is there an extradition treaty in place between the countries?"), the severity of the crime (extradition is not available for minor crimes), and the nature of the crime (extradition is usually available only if something is a crime of similar high severity in both jurisdictions).
The U.S. process and statistics on it, are explained in another Law.SE answer:
Each year since 1990, OIA has opened between 670 to 950 extradition
cases based on requests from U.S. prosecutors and foreign governments.
During the same time period, OIA closed between 380 to 960 cases per
year. OIA's case closure rate has not kept pace with the number of new
cases, resulting in a pending caseload 2 that has increased over 100
percent since 1990. As of November 2000, OIA had 3,636 extradition
cases pending - approximately 1,100 cases where fugitives wanted by
foreign governments were believed to be in the United States and
approximately 2,500 cases where fugitives wanted by the United States
were believed to be in foreign countries.
In theory, felons who flee abroad can and will be routinely extradited to face criminal charges, even in international cases.
In practice, the process is sufficiently cumbersome that it is reserved for the most egregious cases, and even then, it takes a long time to make it happen.
The following example illustrates this point:
A Colorado man wanted as a suspect in a 2016 sexual assault case has
been extradited from Ecuador to Jefferson County. Peter Robert
Dettmer, 69, faces 126 sexual assault charges, according to a district
attorney’s office news release. He was extradited last Wednesday.
Dettmer was arrested in Colorado on June 10, 2016, on multiple sex
assault charges and entered a plea of not guilty on Aug. 29, 2016,
court records show. He then failed to appear for a trial scheduled for
Jan. 23, 2017.
Arrested in Cuenca, Ecuador, on April 27, Dettmer’s extradition was
carried out by the FBI with assistance from the U.S. Department of
Defense, U.S. Department of Justice’s Office of International Affairs
and the U.S. Department of State, the DA’s office news release said.
His is the second extradition from Ecuador to the United States in the
past 27 years.
From the Denver Post reporting on November 30, 2021.
There is little doubt that the extraordinary effort made to apprehend and extradite this man, and Ecuador's willingness to cooperate, would not have happened if the charges the defendant was arraigned for before fleeing to Ecuador had not been so extraordinarily severe under both the law of the U.S. and the law of Ecuador. Ecuador has no desire to have a heinous serial rapist in its country.
Similarly, notwithstanding this fact, it would not have happened if the U.S. had allowed the death penalty for the offense, as in the case in many murder cases, which Ecuador does not.
Rates of extradition also, necessarily, depend in part on the number of cases that come up, with it being rarer between countries between which there is little migration. There are surely many more extradition cases between the U.S. and Canada, for example, than between the U.S. and Ecuador.