There are a couple of routes you can take...
You can write your own list definition where you have defined the workflow association - That way all lists created based on your list definition, will contain your workflow on default.
Or... depending on your workflow... write an EventReceiver your attach to all lists of the type you wish to attach your workflow to (can easily be achieved tru a feature) and have your event receiver associate the workflow when the first item is added.
or you can associate the workflow to the contenttype used in the list (your own contenttype you attach to your own list definition or a default SharePoint contenttype)
I don't know the rest of your solution, so it's defficult for me to suggest the best solution for you.
What I (almost) always do, is write my own list definition - That way I can avoid problems like this, now or in the future.