At this time I've an outdated URL that's getting 404'd:

http://mysite.com/category/?tag=blue-example

It must be rerouted to:

http://subdomain.mysite.com/blue/

This does not work:

Redirect 301 /category/?tag=blue-example http://subdomain.mysite.com/blue/

How do you correctly rewrite this URL?

The mod_alias does only chech the URI path and never the query (the part following the ?). But you should use mod_rewrite with this:

RewriteEngine on
RewriteCond %{QUERY_STRING} =tag=blue-example
RewriteRule ^category/$ http://subdomain.example.com/blue/? [L,R=301]