Is every city/ town/ village in the USA actually in one particular state. Or does a state border ever go through the middle of a city?
What about time zones? Any places where you might cross the street, and suddenly it’s an hour later?
City/town/village is a state level concept, so there are no ‘local’ governments that cross state lines.
There are lots of cities on state lines (Kansas City KS/MO being a good and confusing to visitors example), but they all have jurisdictions that end where the next state begins.
For time zones, I think that major metropolitan areas on a timezone line will generally move it a bit to keep the main population in a single time zone. But sure, there are lots of places where taking one step will move you from 8:00 am to 7:00 am.
If you mean a legally-incorporated municipality with its own local government, every city/town/village exists in just one state. Local government is created by states.
If all you want is a built-up area that crosses a state line, there are plenty of those. There’s Texarkana, Texas and Texarkana, Arkansas; Union City, Ohio and Union City, Indiana; Colorado City, Arizona and Hildale, Utah. There are probably lots more. But they’re all legally separate entities. (Colorado City/Hildale used to have a single police department, with officers sworn on both sides, but I believe it was disbanded by the two states during an investigation into corruption and discrimination. The community is…unique.)
Just from looking around on Google Earth, this little community in Indiana straddles the official boundary between the Eastern and Central time zones. But that doesn’t mean that people observe the difference strictly.
It is possible to have a governmental entity that crosses state lines, and which carries out some local government functions, e.g., the Port Authority of New York and New Jersey, created by agreement between the states of New York and New Jersey. However, that’s not regarded as a city (and in this case overlaps the territory of New York City and several cities in New Jersey).
A population center acquires its status (city, town, borough, etc.) by grace of the state constitution and its laws governing municipality. So, there is no body of authority that is empowered to establish a city whose territory lies in two states. In cases where there is an urbanization on both sides of a state line, each state, independent of the other, establishes the municipal status of whatever entity lies within the respective state.
However, that does not prevent cities in different states from entering into agreements to share participation in any quasi-governmental entities, or to agree to share services that a city is empowered to arrange and provide for, such as fire protection…
If states can create powerful port authorities by compact ratified by Congress, why couldn’t they create joint municipalities by the same method? None have, but is it actually totally impossible if you assume no political resistance?
Don’t forget South Lake Tahoe, California and Stateline, Nevada. No timezone change, but it’s real obvious when you cross the state line! 
Although unrelated to OP’s question, Kiribati (Christmas Island) sets some sort of timezone record. It is 24 hours ahead of Hawaii to its North, and 26 hours ahead of two U.S.-owned uninhabited coral islands to its West.
There are also two interstate school districts Dresden and Rivendell, both spanning NH and VT. These required an act of congress.
There is also UC/CC in Indiana/Ohio that operates somewhat outside the interstate compact law, not really sure how this one is governed. But I love this detail:
Before Indiana joined the civilized world and accepted Daylight Saving Time the towns of Union City Indiana and Union City Ohio would be out of sync by an hour for half the year. The locals called it “Indiana Time” half of the year and yes they strictly held to it.
I worked in Union City Indiana and lived in Ohio. We had a representative from the Franklin Planner company come over and give a seminar on how to manage your time effectively; the company told her to be there at 8:00 a.m. Indiana time. She stayed at the only decent hotel in the area which was in Ohio and showed up an hour late because no one from outside of the local area had any idea what the freak Indiana Time meant.
Someone in my company reported back that she was late for the seminar and she got fired because of it. Damn Indiana Time hicks.
There is Bristol, Virginia/Tennessee, where the center line of State Street is the border between the two states, memorialized in Steve Earle’s song “Carrie Brown:”
I walked around in Bristol town a bitter broken man
A heart that pined for Carrie Brown and a pistol in my hand
We met again on State Street poor Billy Wise and me
I shot him in Virginia and he died in Tennessee
I don’t know of any town or city that is actually divided by a time zone boundary but there are several within about 5 miles of a time zone boundary.
Columbus, Georgia population 198000
Chattanooga, Tennessee, population 168000
Yuma, Arizona, population 93000
Bismarck, North Dakota, population 61000
Pierre, South Dakota, pop. only 14000 but a state capital
I believe the adjacent towns of Wendover and West Wendover along the Utah-Nevada border used to be in separate time zones, but the time zone boundary was redrawn. A few years ago there was talk of redrawing the state boundary too, to put both towns in Nevada, but the plan fizzled.
There are a lot of “paired” towns along the VT/NH border. The border itself is the Connecticut River, and you find a lot of places where there are towns on either side of a bridge. They have separate names and governments, but they often feel like the same town.
In Canada, there is the City of Lloydminster (Sask) and the Town of Lloydminster (Alberta), which do operate as a single municipality via interlocking legislation passed by the two provincial legislatures.
sh-t! ninja’d!
I went to school and lived there; I know it well. But I disagree that they feel like the same town. The difference between VT and NH run deep. 
If you think this is tricky, think about the international date line, where you can gain or lose a whole day as you cross. Of course it should really be 180 degrees longitude, but it has been arbitrarily moved to avoid land masses. This has been altered many times over the years as trading and military alliances dictated. Samoa for example switched in 1892 (repeating a day) and again in 2011 (losing a day).
From Wikipedia, that place (Koontz Lake) is a “census-designated place”. (It spans two counties, and hence, in this area, two time zones.) What does this actually mean in practice? What is the difference between an incorporated place and an unincorporated place? If I live in the latter, do I miss out on local services? Do I pay less taxes?
It’s a bit of a tricky concept to get your head around for someone who lives in the UK. Here, every scrap of land, urban or rural, falls within a local council area, so there’s no such thing as an “unincorporated” area.
Anyway, also according to Wikipedia, Koontz Lake observes CST, the time zone of Starke County, where most of the houses lie. Presumably the folks just across the border in Marshall County also observe CST, but the next village along the road to the east, Tyner, is wholly within Marshall County and so presumably observes EST. Looking at that map, there are houses fairly evenly dotted along that road. I wonder which is the first one to break ranks, time wise? 
Related question: do time zone boundaries always follow county lines in the US?
There’s also the city of Fort Pierre across the river and in a different time zone. Pierre is in Central and Fort Pierre is in Mountain so when the bars close in Pierre, you can drive across the Missouri River and go to the bars in Fort Pierre for another hour.
No.
Some TZ questions can be answered here with some of the legal description of all of the time zones.
Strangely enough I don’t see movement of Eastern Oregon into MST and the whole Indiana thing so I suspect we’d have to go to the Sec’y of Transportation’s website for all of the official descriptions.