Where can I find sample Simplified Chinese mailing address data?
Understanding Addresses
If you want to understand the structure of addresses, this Phonemica post is a good place to start. Turns out it's complicated.
Roughly speaking, it's a hierarchical system working from the top down, from left to right. So, country (optional), province, prefecture level city, small town, district, etc. Unfortunately the levels are not consistent across the board. Some cities are 直辖市 (directly-administered-cities) like Beijing and Shanghai, and as such, they do not belong to a province. Some provinces are called 自治区 (autonomous regions), and their internal structure is different from a 省 (province).
Getting Data
Manually
This is a rather slow process, but go to Google maps (China) or Baidu maps, zoom in or search and drill down to individual addresses.
From Baidu [Note, missing the province and city, which are obvious from the map]:

河东区津塘路互助南里18号楼底商(近二宫公园)
武侯区通祠路39号一江城花2楼（春江花月夜对面）

From Google [Full mailing addresses]:

上海市徐汇区零陵路899号
浙江省绍兴市越城区鲁迅中路237号

Automation
If you want to get a lot of addresses, you're going to need to automate. One approach you could try would be to scrape a website that does reviews, like Dianping.
From Dianping [Same format as Baidu. You have to select a city first, and then all results are restricted to that area, and addresses are relative to it.]:

成华区双庆路8号万象城1楼
江汉区解放大道557号中山广场5楼

Cheers, and happy data-ing!