Obviously, this is not the first terrarium-themed instructable. Inspiration came from noahw's DIY Terrarium instructable, along with ThinkLem's Lightbulb Terrarium and alisha145's Tiny Terrariums. However, I think the wine bottle idea might be a first!
Step 1: Bottles
Your bottles will probably needs the labels removing. Labels are either stuck on with water-based or solvent-based glue. Unfortunately one needs a lot more work to remove than the other.
Start by soaking the bottles in hot water (but not boiling hot as this could crack the bottles) for a few minutes. Labels glued on with water-based glue will either soak off in this time or some gentle pushing with a paint scraper will do the trick. For labels stuck on with solvent-based glue, scrape away as much of the paper as possible (ideally all of it) and give the bottle a rinse. To remove the gummy residue from the solvent-based glue, I used acetone (it's also in nail varnish remover but less concentrated). Practically anything that will dissolve plastic works, although you could just buy some de-gluing stuff from your local hardware store.