Neither local nor state governments in the US have any power to engage in foreign relations. The federal government is the only entity with that power, and so they must be involved in all extradition matters. Countries do not have treaties with the City of New York (for instance), they have treaties with the United States.
Formal extradition requests are made through diplomatic channels; the primary responsibility for all US foreign affairs lies with the State Department. In general, when governments want to talk to other governments, they use diplomats; that's literally why diplomats exist. The State Department coordinates closely with the Department of Justice's Office of International Affairs (OIA); OIA, in turn, coordinates with prosecutors (law enforcement agencies don't write up most of the paperwork, just like they don't write up warrant requests or charging documents -- that's a job for lawyers). For federal charges, the Justice Department requires all requests to go through OIA. For state charges, the State Department likewise won't forward on a request without OIA approval.
There is an exception in some US extradition treaties to the normal "extradition papers go through diplomatic channels" rule: provisional arrests. Those happen before the full formal extradition request is filed, and some US extradition treaties allow the DoJ to request them directly from the foreign justice ministry. Again, though, this is OIA's turf; state and local authorities can't just call up foreign authorities and request a foreign arrest warrant under the terms of an international treaty.
The Texas District and County Attorney's Association journal ran an article in 2012 on the process for extradition from Mexico from a state prosecutor's point of view. They ran another article in 2015, which was a bit more general. The basic process is as follows:
- US officials figure out roughly where the suspect is. They might start with less formal non-extradition alternatives like deportation (if they're a US citizen and not a citizen of the country they fled to, that country may well decide to kick them out and send them back to the US, where US police can arrest them on arrival). But at some point, they decide to seek extradition.
- The prosecutor contacts DoJ OIA to start the ball rolling. OIA looks over the information and advises on whether extradition is feasible or not.
- If it's feasible, then you start to gather the information needed, with guidance from OIA. This may involve coordinating with foreign law enforcement. Unsurprisingly, Texas and Mexico have the infrastructure in place to do some direct coordination; in general, though, federal law enforcement agencies like the FBI, the US Marshals, and the Diplomatic Security Service can also help (because they're far more likely to have a working relationship with foreign police).
- You submit a package to OIA, who decides to request (or not) a provisional arrest. They send it to foreign authorities either directly or through a diplomatic channel, and the foreign authorities review it using whatever procedures they have set up. If everything's good, the foreign authorities make an arrest.
- You get all the details you need for the full, formal extradition request. You send it off to OIA, who sends it to the State Department, who sends it to the US Embassy, who sends it to the other country's foreign ministry, who sends it to whoever deals with extraditions in their country, who analyzes the request (generally in the court system). If the foreign proceedings result in an extradition order, the prisoner is extradited.
Dale M. in the comments mentions a good point: the extradition process can also start with a notification from the country where the fugitive is. One of the ways the state or local law enforcement agency can try to get that is by requesting assistance through Interpol. The state or local agency or prosecutor would contact the DoJ agency that's the US representative to Interpol, and the DoJ can then ask for a Red Notice to be issued. A Red Notice formally tells other Interpol countries that someone is wanted for extradition; if foreign law enforcement comes across them, they're supposed to then notify the US and the US will seek extradition. In some countries, a Red Notice is by itself grounds for a police officer to make an arrest on the spot.
The catch with a Red Notice is that you're saying you will seek extradition. Extradition is time-consuming and expensive, and you have a ticking clock (especially if the country arrested purely on the basis of the notice). However, if someone's in Russia (which doesn't exactly have the best relations with the US), a Red Notice may well be the best way to get them.
