How do I add taxonomy terms and vocabularies to an exportable deployment plan?
I seem to have stumbled my way through to a solution. Vocabularies don't need to be exported via UUID, as they already have their own machine name, but any terms within those vocabularies still need to be added to a deployment plan so they can be exported (inadvertently adding a vocabulary to the plan throws errors). 

Using the latest development snapshots (as of March 14, 2012) of UUID, Deploy, Entity Dependency API, Views and Rules, it is possible to stitch together a UI for adding taxonomy terms to a plan. First, a managed fetch-only deployment plan must be created. 

Next, a Rules component must be created using Rules, with a taxonomy term as a single parameter and a single action that adds the entity to the selected deployment plan. Note, however, that the current development snapshot of Deploy does not allow you to use Rules to add to a fetch-only managed deployment plan (I had to write a trivial patch that allows this behavior). 

Next, one should create a view of all taxonomy terms, adding a Bulk Operations checkbox using Views Bulk Operations. If you have created your Rules component as above, VBO will allow you to select your component as a task to perform on all checked entities. 

Now that your form is configured, all that's left to do is visit the view and add the necessary taxonomy terms, and select the relevant components to export via Features. Gotcha: There is no dependency checking in Features after adding the taxonomy terms via uuid_entities. You have to remember adding the vocabulary yourself, or tragedy and error messages will ensue.