I'm assuming that like most of your other questions, you are more interested in programatically doing this from scratch, instead of doing this in any specific program.
Geocoding & reverse Geocoding is multi-stage process.
First you need to know What kind of addresses will be entered by the User. For large parts of the US, just the ZIPCODE, StreetName & House Number might be enough. To give Options to the users, you could also allow users to enter state & city/town instead of the zipcode. If you want to geocode street corners, the user might enter two street names. The address scheme in Japan is totally different. The Address scheme might be totally different in Europe. Based on all this you need to make sure that the required information is present in your data, and you need to index those fields in a standardized way .
Now you need logic for standardizing the User Input. You need to be able to handle Maple Street & Maple St. Your engine needs to understand the First Avenue is the same as 1st Ave. You will also have to take care of prefixes, and suffixes in the address. You'll have take care of spelling errors.
- Once you have standardized the input, you need to match it with your index. Chances of getting a 100% match are every low. So you need some kind of fuzzy logic to figure out what you consider a match.
Reverse Geocoding is much easier, since you just need to interpolate the location, on the closest matching point, and then figure out the address based on it.
I remember using the Geocoding Developer Kit available from ESRI. It had a nice pdf which described the internals of the geocoding engine. You could go through it for some pointers.
You could also go through the code of some open source geocoding engines to understand how they do it.