How to obtain longitude and latitude for a street address programmatically (and legally)
The term you're looking for is geocoding and yes Google does provide this service.
New V3 API: http://code.google.com/apis/maps/documentation/geocoding/
Old V2 API: http://code.google.com/apis/maps/documentation/services.html#Geocoding
In addition to the aforementioned Google geocoding web service, there is also a competing service provided by Yahoo. In a recent project where geocoding is done with user interaction, I included support for both. The reason is I have found that, especially outside the U.S., their handling of more obscure locations varies widely. Sometimes Google will have the best answer, sometimes Yahoo.
One gotcha to be aware of: if Google really thinks they don't know where your place is, they will return a 602 error indicating failure. Yahoo, on the other hand, if it can peel out a city/province/state/etc out of your bad address, will return the location of the center of that town. So you do have to pay attention to the results you get to see if they are really what you want. There are ancillary fields in some results that tell you about this: Yahoo calls this field "precision" and Google calls it "accuracy".
If you want to do this without relying on a service, then you download the TIGER Shapefiles from the US Census.
You look up the street you're interested in, which will have several segments. Each segment will have a start address and end address, and you interpolate along the segment to find where on the segment your house number lies.
This will provide you with a lon/lat pair.
Keep in mind, however, that online services employ a great deal of address checking and correction, which you'd have to duplicate as well to get good results.
Also note that as nice as free data is, it's not perfect - the latest streets aren't in there (they might be in the data Google uses), and the streets may be off their real location by some amount due to survey inaccuracies. But for 98% of geocoding needs it works perfectly, is free, and you control everything so you're reducing dependencies in your app.
Openstreetmaps has the aim of mapping everything in the world, though they aren't quite there it's worth keeping tabs on as they provide their data under a CC license
However, many (most?) other countries are only mapped by gov't or services for which you need to pay a fee. If you don't need to geocode very much data, then using Google, Yahoo, or some of the other free worldwide mapping services may be enough.
If you have to geocode a lot of data, then you will be best served by leasing map data from a major provider, such as teleatlas.
-Adam