When we think of a temperature, like 72 degrees Fahrenheit, we get an image of our comfort level. Why not do the same thing with degrees Celsius?
Make up a Celsius scale from 0 to 30 with 5 degree increments. Assign labels to each interval.
You can cheat and use Fahrenheit equivalents as a crutch, but don't write them on this scale. Use 0 C = 32 F (or 20 C = 68 F) and add or subtract 9 F for every 5 C change.
It might be necessary to leave some blanks until you experience a temperature range.
You might even be able to divide the 20 - 25 C interval into two subintervals (you choose where) and invent more finely tuned labels for these intervals, but still keeping the label for 20 - 25 C.
Then refer to this scale with your labels when you're trying to get a feel for a temperature given in degrees Celsius. You may even be able to do this without referring to a paper copy, then it will be like speaking and thinking in a new language.
Scroll down for my scale (after making your own).
Note: these descriptions apply when wearing shorts and a t-shirt -- my year-round uniform, useful for any temperatures above 0 degrees Celsius, or limited times below that mark.