freedb.org publishes their entire database for download. You could slurp that into a local database and have the user enter a bit of information, like the artist. Then have the form display a list of possible matches.

For (user) efficiency, you probably want to accept multiple CDs at once. E.g., the user would grab a stack of ten CDs, punch in all ten artists (or fewer with multiple CDs by the same artist), and hit submit. Then give a list of all possible matches, and a checkbox next to each, plus an "it isn't here" button.

Or you could take the opposite approach and have a big, alphabetized list of all of the CDs. You'd probably need to partition it into several pages. If the collection is already alphabetized, this approach could be a big win. Just check the boxes next to the ones you've got, hit submit, and you're presented with the next page.