To begin with, you need to use autonumbering for the appendix titles. Ideally, you will use one of Word's built-in heading styles for these paragraphs (if you have used the top heading levels for other headings in the document, you can use lower-level styles for the appendixes; see http://shaunakelly.com/word/numbering/numberingappendixes.html). In the Define New Multilevel List dialog, select A, B, C numbering to link to your heading style and type "Appendix" before the number field in the "Enter formatting for number" box.
You can then use References | Captions | Cross-reference to insert a cross-reference. If you used a built-in heading style for the appendix titles, select "Heading" as the "Reference type" and "Heading number" for "Insert reference to." If you haven't used a built-in heading style, you can still use cross-references, but you will have to first bookmark the heading, then insert a cross-reference to the bookmark. Cross-references don't update dynamically, as numbered paragraphs do, but they do update automatically when you update other fields, as by printing or switching to Print Preview.