For an advance notice, if you associate a workflow with a document library, then all content types associated with that library will be able to utilize that workflow within that library. So you don't necessarily need to associate a workflow to a content type if it is already associated with the target list.
In no situation can you associate a workflow with a content type on creating the content type. Whether by object model or by UI, you have to add the workflow association after the content type has been fully created. Lookup columns can be associated with content type on creation, but only through the object model. Using the UI, you'll have to add it after creation, just like workflows.
To create a new content type in general, go to Site Settings, pick Site Content Types, and click the Create button in the toolbar. Fill out the form as you find it fit. Now, you can add the workflow association and lookup columns before or after you associate the content type with the list (depending on whether you want the workflow and lookups to be available on all lists that the content type is added to, or just the one document library). The process is the same either way, just a different place.
To add the content type to your document library, navigate to your document library and pick Document Library Settings from the Settings toolbar section. First you'll need to enable content type management if it isn't already by picking Advanced Settings, choosing Yes for "Allow management of content types", and clicking OK. Now, under the section of Content Types you can "Add from existing content types" to select the new content type you made, and click OK to confirm.
To associate the workflow and the lookup column with the content type, you need to modify the content type settings. Pick the content type from the list of content types (whether you are in the Site Content Types list or the content types list for the document library). You can associate the workflow by clicking "Workflow settings" on the content type page and choosing to add a new workflow. You can associate the Lookup column by picking "Add from existing site (or list) columns" and choosing to add the category and subcategory lookup you created earlier. Once complete, you'll now have a content type that is associated with a workflow and has the specified lookup.