If I create a new document and add headings to it, they do not show up in the Navigation Pane. If I open up a document that somebody else created with headings, they DO show up in the Navigation Pane. What gives? Word / Office 365.

Are your headings sitting inside a table? Tables interfere with the 'normal' behaviour of headings in the Outline View and Navigation Pane

__________________
Andrew Lockton
Chrysalis Design, Melbourne Australia

Are you using a Microsoft Template or yours/someone's custom Template?
Are you using a Heading Style?
If a Style is being used, did you verify the Outline Level is set? (Paragraph Settings under the Style.)

See my article: Headings that do not show up in the Navigation Pane or in a Table of Contents (or in Cross-References / Hyperlinks)