I did a post on the Ubuntu Forums a while back on how to update mp3 file tags with a program called EasyTAG. I've tried a few different tag editors and found that EasyTAG best meets my needs. It's available in the Universe repositories in Ubuntu.

Installing EasyTAG

You can install it through Synaptic by searching for the package easytag and selecting it for installation. Or you can do the old familiar terminal installation:

Run EasyTAG

Once installation is complete you should be able to find EasyTAG in the Ubuntu menu under Applications -> Sound & Video -> EasyTAG.

Here's the basic procedure to automatically fill the mp3 tags for a folder of freshly ripped files from a CD.

1. Open EasyTAG and navigate to the album folder which contains the files you want to edit.
2. Click the blue box icon to select all files.
3. Click the CD icon for Search CDDB.
4. Click on Find in the window that comes up.
5. Select the correct album from the search results.
6. Click the blue Select All icon.
7. Click the Apply button.
8. Click the Close button
9. Click on the Save Files icon.
10. Click Yes on the confirmation prompts

If you would like to rename the files like Artist - TrackName.mp3

1. Make sure all your files are selected.
2. Click on the green Scan Files icon.
3. In the new window, select Rename File and Directory in the scanner drop down list.
4. Set the rename field to show %a - %t
5. Click the green icon next to the scanner drop down.
6. Click on the Exit icon.
7. Click on the Save Files icon.
8. Click Yes on the confirmation prompts

Here's a link to some screenshots on the official EasyTAG webpage.