Feature Stapling is really just for out of the box site definitions
A couple months ago, when I started reading about Feature Stapling on blogs (I don't recall the MSDN documentation having been updated at the time but it is now), not only did I think that it was a mechanism to attach a feature to a site definition (it's true) but it was also touted as a way to update a site after it has been deployed. As a little note, Feature Stapling is basically a feature that contains FeatureSiteTemplateAssociation nodes that attaches a FeatureId to a Site Definition name and configuration.
Now I have carefully worded the last sentence. it's still true, you can use it to update a site after it has been deployed, however, what I didn't know is that Feature Stapling will ONLY work on new site that will be created. Sites already created will not have the feature activated on it and will require a different process (custom).
Now that's a little bit more interesting because Feature Stapling simply adds a <Feature Id=... /> tag to site, which you can do in the ONET.xml anytime unless it's an out of the box Site Definition. Since modifying those definitions isn't supported, Feature Stapling is then the mechanism to attach custom features to OOB definitions. For your own custom site definitions, while you can still use stapling, you can also simply modify your custom ONET.xml and it will do the same.
Now, what do you really do to attach the feature to created sites (which is really what you want to do)? Since Feature Stapling or site definition modifications only works for future sites, you need to activate the feature "now" to all existing sites. The best way is to create a custom STSADM extensions that will run through all sites and subsites, validate if the feature's (SPWeb.Features) is there on the SPWeb. If it is, keep going, otherwise, add the feature to the collection and update (and dispose) the SPWeb object. You can use something simple in the lines of :
1: using(SPSite site = new SPSite(http://servername/))
3: foreach(SPWeb web in site.AllWebs)
5: if(web.Features[featureId] == null)
In summary, you absolutely have to use Feature Stapling on out of the box site definitions to add your custom features to it. For your custom site definitions, you can either modify your ONET.XML file or use Stapling. For already created sites, create an STSADM extension to activate that feature on all of them.