In previous versions of Flex (when using Halo), it was simple to add an icon to a button. But now with the Spark theming, there is no such convenience. I went in search of a solution online and after much digging where others had written custom components and so on, I found a solution posted by Adobe and its incredibly simple.
Just create a new theme extending the Spark button skin, and then make two line replacements. Instead of me reexplaining it, just read it on Adobe's website.