I carry bottled water in my trunk, and sometimes it freezes. I haven't really done anything about it other than sometimes having frozen water bottles.
haha! I was going to say the same thing. I've tried an insulated bottle holder for my Nalgene and it works fairly well, but we're down to -31C today, and there's not much you can do about that. I do leave head room in my canteens, and if I remember, I store them on their sides so the bottle opening doesn't completely freeze over.
I have found that those squishy juice packs (i.e. koolaid jammers and those apple saucey things for toddlers) don't freeze as quickly and, because they're hand-sized, thaw quicker and easier.