The Strava climb categorization method is based on the official UCI climb categorization method but with some modifications. When a climb is categorized, for the 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. Strava's method is objective, so if a climb is cat 1 it will always be a cat 1 climb. To decide the category of a climb Strava multiplies the length of the climb (in meters) with the grade of the climb. If that number is greater than 8000 then it is a categorized climb.
Cat 4 > 8000
Cat 3 > 16000
Cat 2 > 32000
Cat 1 > 48000
HC (Hors Categorie) > 64000
You will see that a segment is categorized by the number on 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, 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 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.