You can do this in Illustrator. Look up 3d mapping. It's fairly rudimentary, but should be enough for your needs. You could also probably find a free 3d model of a wine bottle - Google has a pretty large library. Then you could do it in Photoshop.
Photoshop CS4’s 3D-features include a small library of basic forms, including Cylinder, which should suffice for mapping the labels onto as the bottles themselves seem to be photographs.
Edit: Just to make sure, the 3D-features are only available with Extended as far as I know.