First, you should be able to build a workflow on a SharePoint site, and then save that site as a template to include the workflow in any new sites built from that template. I know I've done that before.

However, you should also be able to export the workflow and import it to an already existing site. You will probably have to go through the workflow and repoint some, if not many, of the references used, but it will save you a lot of time.

Alternatively, you can also save the workflow as a snippet, and then build a new workflow on each site using your snippet.