When I first tried vegetarianism in the 70's, the whole "complete proteins" thing was to eat the different amino acids at each meal. Beans and rice are a good example-each has a different set of aminos.
Amino acids make up the complete protein chain, and while plants don't offer every one, the good, and most important news, is that the human body makes the ones that are missing by the combination of others. It is also now known that we don't need to "chain" the different aminos at each meal, but simply to insure we eat the variety of protein sources through the day (maybe days even?).
Here are some great sources of info:
You may find a lot of us pointing to vegan information, that's all encompassing, and a good foundation whether you eat dairy or eggs or not!
Don't let the perfect be the enemy of the good
Oh, soy is a complete protein. I think quinoa, a seed, is too, but I'm not sure on that one.
Another thing people misunderstand is how much protein we really need, and that if you eat enough calories of good food (opposed to junky, sugared processed stuff), you're bound to get enough.
When they say things like broccoli has more protein than meats - it's by calories, not weight. If you think about it, humans being the ever growing bellies that we've become need more foods that aren't so nutritionally dense by weight.
Don't let the perfect be the enemy of the good
If you are a holistic veg*an, meaning you don't consume processed foods then finding protein sources is pretty easy. Eventually your body will acclimate to your diet and pull proteins from things you didn't normally look to for protein. For instance, all vegetables contain a small amount of protein, especially dark green vegetables (like broccoli) and avocados. And just like Silva pointed out, they are incomplete forms, but if you are eating well rounded meals they will complete themselves.
Quinoa, soy products (including miso), beans and legumes are all complete protein sources.
“The real satanist is not quite so easily recognized as such” - Anton Szandor LaVey
The biggest misunderstanding is that plant proteins lack certain amino acids we need. This myth is helped along by the clumsy terms 'complete' and 'incomplete' protein. All plants have all the amino acids we need.
What 'complete protein' actually refers to is a dietary protein very much like eating human flesh. Pig, cow, and chicken meat is remarkably similar to human flesh so in a hypothetical starving population who can only get 20 grams of protein per day it would be far better if that protein matched the flesh the body was trying to make from it.
'Incomplete protein' refers to a protein source in which the relative amino acid concentrations are significantly different from human flesh. Imagine you were trying to make a bags of 10 blue marbles and 10 red marbles (human flesh) and you were given cups each containing 10 blue marbles and 10 red marbles (a pork chop). It would be easy! But imagine each cup had 5 blue marbles and 15 red marbles (millet) you'd need twice as many cups to make each bag and you'd have stuff left over. If trying to survive with millet (one of the most 'incomplete' grain proteins) as your only real protein source you'd need to consume almost 5 times as much millet protein to get enough lysine compared to if you were eating a pork chop.
Different plant foods can be out of the human-flesh balance due to different amino acids. Grains tend to be short on lysine but legumes have lots of that and tend to be short on methionine, so combining the two lessens the total amount of protein you'd need from either source alone. Hence wonderful dishes like red beans and rice or peanut butter sandwiches.
But to make things easy, as the fall and silvia indicated, if you eat whole foods without tons of sugar and fat then just getting enough food ensures you have enough of the amino acids. For instance in world war 2 some people survived on nothing but potatoes and sauerkraut for a whole year and in asia many people thrive with rice as the dominant protein and calorie source plus some veggies for vitamins and with small quantities of fish used more like a spice. The idea of people not getting enough protein comes from the dawn of modern chemistry after protein was discovered but before calories were discovered, it referred to people who simply didnt have enough food.
Theres cool little graphs that show relative concentrations of essential amino acids in food proteins.
In the 'protein quality' graph pork has a near perfect score, its like eating uncle bob:
And heres millet, a very 'poor' protein, you can see it has Lys (lysine) but it has much less relative to the others.
Brown rice supplies lysine in a far better balance relative to the others
Thats a fun website to poke around.
silva's reference to veganhealth.org is a good one. Here is the specific article about protein that explains the difference between "complete" and "incomplete": http://veganhealth.org/articles/protein
So here goes. Basically our bodies need a certain set of amino acids. When all those amino acids are easily available in one food source, that is called a "complete" protein. Our bodies can derive the amino acids they need from a variety of food sources and they do not need to all be present in one food source but in the past it was wrongly believed that humans needed to consume all the necessary amino acids in one meal. But we can eat a variety of foods that contain some amino acids here and there and our bodies will be able to string them together to create complete proteins.
The best way to ease any fears of protein deficiency on a vegetarian or vegan diet is to consume soy foods regularly (tofu, edamame, soy milk, etc.).