How can I get Chef to run apt-get update before running other recipes

You can include the apt recipe in the very beginning:

include_recipe 'apt'

this will run the update command.