We have a question about how to label things for the freezer in general, but that's for if you've managed to plan ahead. What if you have a bag in the freezer, already thoroughly frozen, so tape doesn't stick well and markers don't write well? What's a good way to label it at that point?
If you can’t get the marker to work, just add another bag around the old one.
Get a piece of paper, preferably a bit thicker. Write on it with black marker. Wet small part of it with warm water and stick to the frozen thing. The water will freeze acting as a glue.
I've used freezer bag clips labelled in marker or chinagraph pencil. You could write on a room temperature clip then swap it for whatever closure you use, or add it to a tied bag. To reuse, chinagraph comes off with a wet cloth (e.g. washing up), most markers come off with alcohol (surgical spirit for example).
Some marker pens do work so long as you wipe the bag immediately and write fast before condensation forms.
I usually wrap my freezer bags with some brown paper (similar to what you'd get from a butcher). This lets me label the front and sides, because I often need to put frozen stuff side-up as I'm rotating things in the freezer.
So, you can just cut a brown paper bag so it wraps around whatever you need to label, and a tiny bit of tape to secure the ends of the paper once it's around your frozen bag.
Also comes in handy to see if your freezer was off for a period of time, as you'll see watermarks on the paper if anything managed to thaw more than a tiny bit.