The answer to this could be VERY broad in that it really does depend on what you want it to do. Generally, the way a complex geocoding system works is there are multiple layers that the geocode operation runs against, in a specified order. So, for example, many of them will look and try and match the input up with a point of interest by name, then it'll try and match against address points, then it'll try and interpolate an address by a road, and finally it may resort to using generic community name &/or zipcode matches. Furthermore, many of these will have some sort of threshold system set up for each layer, such as allowing a low match tolerance for POI matches because someone may have slightly mis-spelled something (matching Bob Mountain Range with Bob Mountains), but having higher tolerances for addresses because you don't want it to take you to West Main St instead of East Main St. So, when you type in an address to geocode, it will search these different layers, in order, looking for matches and will return the best match from the first layer that returns a sufficiently precise match to meet that layer's threshold.
Now, I say all that because reverse geocoding can work very similarly, if only in reverse. Instead of the user providing an address and it doing textual searches through attribute tables of layers and returning the geometry of matching features or interpolated geometries; you provide a location and it searches the geometries of various layers and returns the attributes or interpolated attribute of a nearby feature. However, a complex geocoder should be able to support complex reverse geocoding as well. Just as you can set tolerances for geocoding, you should be able to set layer specific thresholds for reverse geocoding. So, just for example, you provide an input XY location and it searches within, lets say, 0.75 mile for a matching POI. If no POI is returned, it looks within 0.5 miles for an address point. If no address point it searches within 1 mile for a road to interpolate an address from. If no road it searches within 10 miles for the closest zipcode or city center. Now, that is just an example, but hopefully it gives you some ideas in setting up your new system.
Hope it helps, let us know if you still have questions.
You cannot legally cache or store results from Google's Map API (with pretty narrow exceptions).
From the Terms of Service (with emphasis added):
10.1.3 Restrictions against Data Export or Copying.
...
(b) No Pre-Fetching, Caching, or Storage of Content. You must not
pre-fetch, cache, or store any Content, except that you may store: (i)
limited amounts of Content for the purpose of improving the
performance of your Maps API Implementation if you do so temporarily
(and in no event for more than 30 calendar days), securely, and in a
manner that does not permit use of the Content outside of the Service;
and (ii) any content identifier or key that the Maps APIs
Documentation specifically permits you to store. For example, you must
not use the Content to create an independent database of "places" or
other local listings information.
So option 1 it is, unless you only use the geocoding for the purposes described in the Maps API ToS, and only temporarily cache.
Best Answer
Reverse Geocode Tool Documentation.
Your data needs to be in a format that ArcGIS will recognize as a layer (shapefile, geodatabase feature class, etc.). If you just have XY's in a table, consider adding your table to ArcMap then using the add XY data tool to create a layer you can use in the reverse geocode tool.