I was vegetarian for 9 years. You can do just fine -- tons of stuff are protein sources, including many grains (like quinoa,) nuts, beans, tofu / soy products, and of course whey supplements and eggs / egg whites (unless you're vegan.)
The key is that most veggie sources of protein are incomplete (except soy, I think, is a pretty complete protein) so you need to mix and match -- beans with leafy greens, for example -- to get the full set of aminos.
It's certainly *easier* if you eat meat; getting a lot of complete protein as a vegetarian requires some research and some meal planning (or just a lot of protein powder, which frankly I resorted to at times when I was lazy.)
Still, much of the protein I eat now that I am not vegetarian is still vegetarian. For breakfast I have some whole wheat toast with good peanut butter on it and a fried egg, or a couple fried egg whites. I drink protein shakes after workouts. I eat a lot of soy, greens, etc.