hi MTKM,
we went on a 2 week trip to beijing, xian and shanghai few months back. we are vegetarian too...here is how we managed..
1. carry heat and eat food like others have suggested
2. i googled for list of vegetarian, italian and indian restaurants and took print outs of them...the travel guide sites to each city has a list of restaurants both in english and mandarin
3. there is a good list of vegetarian chinese food list, here's the link
http://www.vegetarian-china.info/
4. carry nescafe 3in1 coffee sachets...it is hard to find starbucks in china
5. we had vegetarian dumplings made of spinach and tofu practically for all meals...it is yummy