At Backlane we soak all our new bottles in mild bleach solution for a couple of days to remove labels, and give them a quick scrub with a plastic scourer to remove any glue left behind. Some are easier than others- Boags, for instance, are a real pain.
We came up with a standard format label, just need to choose colours/pictures & fonts as appropriate. After much artistic & creative agonising we print the labels on a PC, get 8 to an A4 sheet. After cleaning the bottles again, we use a spray adhesive to attach them. If you spray a thin coat and wait a minute or two they will stick well but are easy to remove, with no soaking.
We usually only label a few from each batch, and make a point of keeping the best looking one on the mantlepiece (which is getting very crowded)
We mark caps in felt tip too, have a master list of codes somewhere so we know what's what, but clean these off when the bottle is labelled.
For what it's worth, we think naming and labelling can really "make" a brew, especially if you are giving it to someone. Handing someone a sparkling clean bottle of "Happy Otter" with a label on it seems to go down better than just giving them a dirty bottle of anonymous brew.