All traditional cheese is non-vegetarian, but some kinds can be made vegetarian.
Rennet is a combination of a bunch of enzymes, made in the stomach of ruminants such as cows. It's used in cheese-making to help separate the curds from the whey. It's most often sourced from slaughtering juvenile cows.
However, rennet can also be sourced from GMO micro-organisms and certain fungi/bacteria, and thus can be vegetarian/vegan. Most cheeses can substitute traditional rennet for this vegan kind.
But some cheeses, for example Parmesan (in the EU at least), have to use animal rennet. This is because for a cheese to be called Parmesan, it has be made using a traditional method that uses animal rennet.
This particular example only applies within the EU, but I'm certain there are other cases I don't know about.
I have been unable to find a list for which cheeses need animal rennet though.
TL;DR: only buy cheese that says it is vegan/vegetarian and doesn't contain animal rennet.
Also, cottage cheese, cream cheese, and other soft cheeses often don't need rennet. They may contain gelatin though, but you'll have to check the label.
Edit: As Will helpfully pointed out in the comments (that I just now saw, sorry about that), http://cheese.joyousliving.com/ has a nice list of veg*n cheeses.