I happen to work at the company that handles most of the CD data lookups in the world (Gracenote), so I can tell you that you'll probably want to do what Khar said: stick your CD into a computer and open it with a current version of a music player that is NOT Windows Media Player (like iTunes, but I believe WinAmp also works). I don't use WinAmp, but here's how to do it for iTunes: If you stick the CD in and no data comes up (which, if no one's listened to the CD yet, should be the case), then you should use File->Get Info to view track, album and artist data and edit it as necessary. To save time, you can first select multiple tracks, select "Get Info", and add your band's name, the album name, the year, and the genre. Do us a favor and Capitalize The First Letter Of Every Word.
Then when you've entered all the album, artist, track, genre, year data, you can select Advanced->Submit CD Track Names, which will use our Submit tool to send the album data to our CDDB. It will take between 15 minutes and one day to get the data to appear on CD data lookups. You should test whether or not this worked on another computer, since iTunes and other players usually keep a cache of the custom data you've entered.
You will probably have to do this for Windows Media Player as well, since it's the only major music player app that doesn't use us. I'm sure WMP has a very similar Submit utility that you can use much in the same way as the iTunes utility.