see freedb "submit new entries" howto:
http://www.freedb.org/en/download__miscellaneous.11.html
Basically you can use email and HTTP POST submission but for details see the doc.
Also email method with example described here:
http://ubuntuforums.org/showthread.php?t=1669680&p=10883530#post10883530
basically best is to use some program to do it for you. But I couldn't spot any searching now half an hour.
UPDATE:
Option 1: I managed to update freedb. Use grip to generate the file in ~/.cddb/diskid, you can grep in the dir for it. I couldn't upload with grip perhaps because local mail is not setup. If you have local mail program working, you could as well use the cddb-tool to send email to server.
Then I went to gmail, create new message to freedb-submit@freedb.org with subject cddb folk 0510db11 where you change folk to your CD genre and use the proper disk-id. Copy paste the cddb file into the message body. Switch to plain-text format. Last thing is very important. And it worked!
Option 2: use musicbrainz.org. Install picard. Open it and lookup CD. Then click manually lookup CD. There is a link to simple upload. Click it and enter CD information. Then create an account and click on the stub page you just created import as MusicBrainz release. Then enter a lot more information and you are done. Both things work for me. I wouldn't call that very easy...
If I knew everything, maybe option 1 is little easier as long as you are comfortable using command line and properly send the email. Option 2 is easier for GUI lovers.
Finally tested with k3b and it can download CD from both sources. I wish somebody created a freedb submit form..
P.S. FYI the test freedb email did not work for me. I've got no reply.