I've tried a bunch of things over the years, and after a number of lost tags, inks faded to illegibility, and things that have fallen off my carboys resulting in confusion on exactly what I've just bottled, I've started using the lick-and-stick labels that came with one of my wine kits, there's enough room on the tag to record the type and start date (since I occasionally haven't bottled last year's crabapple/red currant/etc/ wine before I've started this year's), I also now add SG and racking dates to the labels to match my brewlog, if I only wet the label's corners or down the sides, it pops off easily enough and can be affixed to the next carboy when I rack. I've usually got between 40 and 60 gallons on the go at a given time so I label everything with the occasional exception of JAO when the fruit's still in it (I can tell the raspberry from the orange!), but as soon as I rack it, it gets labelled.
My brewlog contains everything I've done, in order, on looseleaf in a duo-tang (which is getting pretty fat now, I may eventually start archiving stuff that's been bottled for a year already), but I've made a spreadsheet index for it so I can locate something by its ingredients and date without having to flip through everything in the book to see if I meant THIS blueberry mel or THAT blueberry mel.
