1. Open ArcCatalog (the yellow cabinet icon in ArcMap)
2. Click on "Address Locators" in left nav window
3. Dbl-Click "Create New Address Locator"
4. Select "US Cities With State (File)"
5. Click OK.
6. The main thing you need to do now is select your reference table. I have an address locator called USGS Cities 2000, which uses this file: citiesx020.shp I'm pretty sure if you Google that you will find it is publicly available.
7. Also be sure to name it (first field - upper left).
8. Set other options (probably best to leave these alone for now). Click OK.
Now you have the geocoder created. Go back to ArcMap.
Go to Tools -> Geocoding -> Geocode Addresses.
Click add, click the drop-down file bar, scroll towards bottom of list, choose Address Locators. Select the one you just created. Click OK.
Now you are at the "Geocode Addresses" wizard. Select your address table. Match the city/state fields with the field names in your address table.
That's the basics!