The trickiest part of this is making sure the brand gets used for all new mysites created from this point on. To do so you need to make sure your branding conforms to a key prerequisite. Is your brand packaged up in a visual studio .wsp and can it be applied to a given site collection by activating one or more features? If so then you can apply it to all future mysites using a technique called Feature Stapling.
To use this technique, first create a new feature inside of your sharepoint solution. It should be a Farm scoped feature. Call it something like "MySiteStaperFeature"
Then in your solution create a new empty sharepoint Elements file called something like "MySiteStapler". In the Elements.xml file for this element put the following code
<?xml version="1.0" encoding="utf-8"?>
<Elements xmlns="http://schemas.microsoft.com/sharepoint/">
<FeatureSiteTemplateAssociation Id="<Your Branding Feature ID>" TemplateName="SPSPERS#0"/>
</Elements>
This code will tell sharepoint that whenever a new site is created using the mysite template (SPSERS#0) that sharepoint should automatically activate the feature with corresponding ID. If you have to activate multiple features for your brand, create additional FeatureSiteTemplateAssociation elements, in the order that the features need to be activated.
Add this new SharePoint element to your MySiteStaperFeature. Then you can deploy your solution, activate the farm feature, and your branding will be applied to any new mysites.