We make beer.
We occasionally make labels for that beer.
The easiest, best cheapest way to attach the labels is... ready for this... you sure???
Don't know why, don't ask why. It works. You won't be able to wash the bottles without the label coming off but if you're brewing, by the time you're washing the bottle, you probably want the label to come off.
Because you're getting the entire label wet, it will evenly discolor but I haven't had major issues with the colors running or smearing. There's a helpful guide for it on "OnlineLabels.com". They even have a comparison photo of a sticker label next to a milk-application.
Of course, they want you to buy their labels, so they make it sound onerous to do the application process. We've done a full 5 gallon batch pretty easily, so don't be too concerned about it. And if you try it once and hate it, well... you could switch to sticker paper. Apparently a lot of people use Avery brand sticker labels (the ones you might use for mailing).
Based on their instructions, they have you dip the paper in the milk... we found it was much easier to use a basting brush (or a cheap 1-inch chip brush from the hardware store) than to try to dip the paper.
For other options, see the related/identical question to this on our Homebrewing site - here. This answer, specifically, talks about using milk.