Are the results of Word JS API search sorted?

Can I safely assume body search results are sorted by order of occurrence in the body?

I.e., will context.document.body.search("cat"); always return the first occurrence of cat, followed by the second, followed by the third, etc.

Yes, try to run the following code under the debugger attached:

// Link to full sample: https://raw.githubusercontent.com/OfficeDev/office-js-snippets/prod/samples/word/25-paragraph/search.yaml
await Word.run(async (context) => {
  const results = context.document.body.search("Online");
  results.load("length");

  await context.sync();

  // Let's traverse the search results... and highlight...
  for (let i = 0; i < results.items.length; i++) {
    results.items[i].font.highlightColor = "yellow";
  }

  await context.sync();
});