Most Americans get way more protein than they need, and if you eat a reasonably varied diet you should have no problem. The old myth of protein combineing has been long discredited- once again, a varied diet is all you need. Most vegetarians are able to easily get the nutrients they need with little special effort. However, if you are concerned, these are big protein sources for veggies:
Cheese- It is high in fat and not very good for you, but it’s yummy and easy and it usually ends up a staple. I get most of mine in the form of pizza, enchiladas and nachos. Yum.
Eggs- When I’m jonesing for protein, a couple of scrambled eggs will do it. For dinner try an omelette or a quiche. An egg salad sandwhich from 7-11 is just about the only reasonable veggie meal you can get from there.
Beans- This is my big staple. They are cheap, nutritionally excellent, and pretty much the world’s perfect food. They can be a pain to make, but canned beans are a good way to start. If you have a pressure cooker, learn to use it and you can have beans in 45 minutes. Don’t worry about soaking them- that is pretty much a myth. I just cook mine for three hours in a big pot with spices, onion, garlic and tomato sauce (and I like black beans best.) Some people have trouble when they start eating them, but if beans are a regular part of your diet your body will get used to them. I eat most of my beans with rice, in tortillas, or on nachos. As you can see, Mexican food is great for vegetarians.
Tofu- I’m not big on tofu, but it is cheap and healthy. If you want chewy tofu, make sure to get the firm kind- I honestly have no idea what to do with the other kinds. I cut mine in to cubes, saute with a lot of seasoning, and cover it in a can of sauce from Trader Joes and maybe throw in some frozen veggies. If I am lazy, I slice it and bake it for an hour covered in sauce or seasonings. It’s not very good, but it’s food. I’ve also cooked it on a forman grill, which is also not very good but is edible if seasoned right. You can also spend infinite money on yummy things like pre-made baked tofu and meat substitutes. If you do want to do the fake meat thing, Chik Patties by Morningstar Farms are some of the best things to eat out there.
I think soymilk has more protein than regular milk, and vanilla soymilk is yummy in cereal and coffee. If you have a Trader Joe’s nearby, that is the cheapest place to get it.
Also, peanut butter is a decent (but fatty) way to get protein. I’d supplament your salad with a peanut butter sandwich. I wouldn’t worry too much about fat unless you find yourself eating a lot of cheese and junkfood (a trap a lot of vegetarians fall in to- a veggie diet isn’t neccesarily a healthy one.)
The trick to veggie food is it is usually a lot like regular food except without the meat. Most of us don’t eat bizarre nut loafs and odd tofu dishes. Some cusines are better suited to it than others. Mexican food works well (although if you are picky you’ll want to watch out for lard in the beans and chicken stock in the rice), Italian is easy, most Asian food is easy although it can be hard to find veggie options in cheap Chinese restraunts. Most restraunts have gardenburgers and if that gets boring you can usually get them to substitute a gardenburger into their fancy burgers with lots of crazy toppings.