You can get a replacement CD directly from Palm by calling them and providing the serial number. If the unit was previously registered, they'll want the registered user's name so I hope you got that as part of the transaction. If the unit wasn't previously registered, you can register it in your name. The cost is about $10 US and is done to both help prevent stolen units from being sold and to protect the copyrighted software that's on the original disk.
I have no idea what proportion of units offered on e-bay are stolen but certainly some percentage are. I would be very wary of buying a unit from someone who didn't have the CD. He could either just be sloppy and disorganized, which means he probably didn't take very good care of his Palm, or you could be buying a stolen unit.