First off, I'd strongly consider asking why this has to be off a CD without any kind of installation. One main reason to ask is to make sure that everyone understands that the database could not be updated. If they are under the impression that it could be updated, you would have a major problem.
Also, if you know the reason why and explain it here, it might jolt loose a few more suggestions from the forum here.
You might also clarify whether this would be VB6 or VB.NET. This might get you some more focused suggestions.
Going with what you describe, I'd suggest that you have the VB app connecting to a Microsoft Access database.
As someone else pointed out, you build both on a hard drive so you can make all the changes you want (and test, of course). Then when you are ready to publish, just burn the executable and .MDB file to the CD.
I suggest doing an early test of this by creating a skeleton database (with some data for testing) and a VB app that simply opens the database and displays a couple of records or something. Burn it to a CD to be certain that things work as expected. There may be some additional work needed to open the database from a CD that might not be required when opening it from a hard drive.
Have the database (.MDB file) stored in the same folder as the VB executable itself. This way, you can use functions in VB to determine the folder where the executable is; this will also be the folder where your database is. From within VB you can use this information to build a DSN-less connection to the Access database.
Alternatively, you might just prompt the user to enter which drive the CD is in. All you would really need to know is the drive letter in this case. The path on the CD is fixed, so the only real variable is the drive letter.
Yet another alternative is to simply go through every drive on the client machine searching through the file system for the database file. Be careful with this, though. The thought occurs to me that this might just trigger some anti-virus heuristic monitoring.
Using the DSN-less connection will allow you to open the database via whatever connection you would use (ADODB, for example) without having to set up anything on the machine.
Also be aware that it is likely only one person could use the CD at a time. If someone tries to share their CD drive so everyone can use it once, there will likely be problems. The first person into the app might put a lock on the entire database and this would block anyone else from getting in.
Of course, you might be able to open the database and load the data into memory and close the database. Then you work from the in-memory data. This might help alleviate the problem described above if it can be arranged that they don't all go in at exactly the same time. Or you could have your app pause a few seconds before trying to load again (or any number of similar tricks).