I also use greg-*@domain instead of *@domain, since their docs claim that setting up *@domain tends to attract more spam.
It's not cheap from PM, and there are loads of hosting providers that will provide catch-all email for free with your hosting package (but with some usually pretty poor webmail client) or if you use a mail client it should work too.
I like having good webmail and mail app and other things so I pay, but there are plenty of good options available. Sadly self-hosting email server is not really an option for a variety of reasons, but you should easily be able to use catch-all e-mail addresses.
At some point, I need to migrate away from google and build out my own personal mail server.
The one exception is Craigslist; if I email someone with my normal email, I never get a response. I always use gmail for that.
It's a freemium model, but I've never needed anything in the paid tier