I'm not sure, but is that palm muting?
At 0:09-0:13, it doesn't look like he was palm muting.
If it is palm muting, is it just practice I'm lacking why I can't seem to reproduce it well?
It sounded like palm muting, but
has a live version (@1:00) and the strumming is picked and it is muffled, so, I am guessing there is a pedal or massive EQ shelving.
That is palm muting (and probably finger strumming), but bear in mind it is a produced version where they can filter it, compress it, and EQ/volume duck it massively.
That sound can definitely be achieved just with palm muting. Practice, practice practice. :)