Our categorization is based on the official UCI but with some modification. When a climb is categorized, for Tour de France for example, there is a subjective component to the categorization. If a climb is at the end of the stage it could get a tougher category than if it was earlier in the stage. Our categorization is completely objective, so if a climb is cat 1 it will always be a cat 1 climb. To decide the category of a climb we multiply the length of the climb (in meters) with the grade of the climb in percent. If that number is greater than 8000 then it is a categorized climb. The minimum percent grade must be 3% or higher. So, for a 4% avg grade climb, it has to be 2km at least to be categorized. Cat 3 > 16000, 2 > 32000, 1 > 64000, HC > 80000.
You will see that a segment is categorized by the number icon at both the segment page:
...And at the list of segments on your activity page.
Strava segments are automatically categorized as a climb if the data fits our criteria. The categories are 1-4, with HC being above a category 1 climb, and HC being the hardest category of all. Strava segments can be generated two ways - as a user, you can create a segment from any data on the site. If the the data you choose for a segment fits into a categorized climb, you'll see a red icon on the finished segment with either the number 1-4, or HC. If you are the riding new territory where no Strava data has previously been recorded, Strava will auto-detect and auto-create categorized climbing segments for you.
Here is some more information on Strava Segments.