Use the Variant Tagger app, which is part of the Power Tools Suite - this will tag your products based on the variants and will handle when they are sold out. It also integrates very well with the filter menu, allowing simple and easy setup. Full details are in the Variant Tagger help file.
Method #2 ('old' method)
The trick to getting the filters to work with variants is to create a number of collections for each variant type that you want to filter on (e.g. Small, Medium, Large) with the rule 'Variant Title equals Small' and so on. Check that these collections have the correct products, then add them to the filter menu. This will enable you to ensure that only the products with a matching variant are shown.
Since these rules will also match products that have a variant even if it has no stock we need to take more step. To fix this there is an option under the 'Hide Sold Out' menu item called 'Delete Sold Out Variants' - make sure this is ticked. This will then delete any variants that have no stock which will ensure that the menu still works correctly. This is a feature of the Smart Delete app and is also included in the Power Tools Suite.