Yes that's possible & actually quite easy!
Promotions > Shopping Cart Price Rules > + Add New Rule
2nd tab "Conditions" (The products of which the subtotal has to = more than $100)
Here you can choose a category or categories if for instance you want to give a free hat (Cat 4) with the purchase of $100 of shoes (Cat 3), then you can select category 3 here. If no category, just add "Subtotal equals or greater than 100"
& now 3rd tab "Actions" (The products on which the discount will be applied)
First you set the discount:
Apply: Percent of product price discount
Discount amount: 100 (100% of the Cat 4 product will be free)
Maximum Qty discount is applied to: 1
Discount Qty Step (Buy X): Leave blank
No to all 3 others
Then you'll Select the product that is free (Cat 4) on this tab
You will still need to tell your customers to add the hat to their cart (It won't be automatically added). If you need it automatically added, this extension does the job and is really cheap! I'm thinking of adding it to my site myself