When I was in undergrad (early 00's - Not that long ago), "geocoding" basically meant "linear referencing".
Linear referencing refers to taking a linear feature and returning a point some percentage along its length. For example, you take a database with the coordinates of roads and a record of the start and end address numbers for each segment, zip code, etc. (If I recall correctly, the US Bureau of Transportation Statistics used to provide a very nicely formatted shapefile for exactly this purpose.) It's quite easy to naively interpolate an address to a specific location from this. You can even easily incorporate odd/even road side designations, etc.
Unless, of course, you're somewhere where the address system doesn't work that way. (i.e. Most of the world.)
Now geocoding systems actually work for other countries. Therefore, they're amazingly complex and really interesting beasts.
For that reason, geocoding has mostly gone to a SAAS model. You can still build your own geocoder, but people have come to expect it to actually work.
It's interesting to see the change, at any rate.
I think Google has gotten a bit more advanced by basically doing OCR from street view to make a non-linear relationship along roads. The US address system is still fundamentally a linear referencing system, though. Interpolating between endpoints is how it works.
There's still plenty of incorrect information out there in databases, though.
For example, all the addresses on the street I grew up on are on the opposite end of the road due to the record in the BTS shapefile I mentioned having the start and end addresses reversed. That error has propagated through Google, Bing, and everything else I've seen.
Many years ago I worked for Vicinity Corp., an early maps-on-the-Internet startup (who made the MapBlast site and was the original provider of Yahoo Maps, but was eventually smashed by MapQuest and later Google Maps).
Along with Eddie Babcock (one of the many Vicinity people who came from Atari), I worked mostly on the geocoder portion of the site. It was as fun and interesting as this post makes it sound, with lots of algorithmic work and special cases to make some sort of "human sense" out of the map line data (provided by Etak at the time) and POI database (we had multiple providers for this, a lot of the work I did was creating a unified API into all the different providers).
It is kind of amazing to consider how ubiquitous this technology is now, and almost difficult to remember what it was like (though it wasn't long ago!) when I didn't have a constantly updated map of virtually the entire world in my pocket.