I've had opertunities to work with a number of different GIS packages in the past (see my post comparing a few). Most of them are great but they all cost a lot of money to use. If you trying to get your feet wet and don't want to spend money on one of the real services there are a number of places where you can start like yahoo or ESRI. These free services however have strict rules about using them for any commercial venture. So if you wanted to do geocoding for something that you charge for you need something else.
That something else could be one of the few open source applications that have sprung up. The first one has been around for a good while: geocoder.us. geocoder.us is has a free web service you can use to do your geocoding and they also give away the software they use to do it for free. The code they use to do all the work is in perl so it should work on a number of platforms (they also have a blog with some PHP examples). The second choice would be a newer entry SRC Open Source Explorer Geocoder. The code for SRC Open Source Explorer Geocoder is windows only for now but maybe someone will come along and port it to Unix. Now for the bad new. Both of these applications need a source of data and the most likely source of data for the average joe would be the US TIGER data. The TIGER data isn't too bad but it isn't great and not nearly as good as a purchased dataset. But you can't get better than free so if you are interested in a way to do free geocoding without comercial use restrictions then geocoder.us or SRC Open Source Explorer Geocoder are good places to start.