In biology, organisms are grouped into a set of categories called, for some reason, kingdoms. These are, of course, somewhat artificial, but the need of biologists to categorise is shared by vegetarians and vegans; so much so that we can use the biology concept of kingdoms to say what it is we eat and do not eat.
In general, vegetarians do not eat animals.
In general, vegans do not eat animals or substances derived from them.
Mushrooms are not in the animal kingdom - they are fungi. They can be considered vegetarian and vegan because they are not animal or animal-derived. A related questionsquestion asks Is yeast-risen bread (or other baked products) vegan?.
Thinking in a more qualitative way about why veg*ns might be OK with eating mushrooms, I suppose we might not feel compassion for mushrooms or other fungi because, for example, they don't express any obvious distress about being chopped up and eaten.
From the other angle, why might some vegetarians not eat mushrooms, aside from personal reasons as suggested by Ed Grimm's answer, I think many people are not aware of what is "officially" vegetarian, and aren't sure whether mushrooms are plants, animals, or, as I've heard people say, "something in between" (from the biological classification perspective, they are neither). A vegetarian might want to follow the rules but may be unsure what the rules are (because there aren't any, really).