I haven’t come across any recommended method of deploying a theme with a SharePoint solution, but here’s a suggestion that should work: Simply deploy all the theme files to their relevant location in 12\TEMPLATE\THEMES using the TemplateFiles element (ok, maybe this is the recommended way .
You’ll also need to deploy an updated copy of 12\TEMPLATE\LAYOUTS\1033\SPTHEMES.XML. I’m not sure if this would be supported as you’re overwriting a core SharePoint file in your deployment, but it’ll do the trick. You would have to modify this file manually anyway I suppose (although there’s the risk that your deployment could overwrite previous themes added manually in this file by someone else).
As far as I know, there’s also no out-the-box method of applying the theme automatically to a site. You could write a feature event receiver to do this though via the SharePoint API.