How do companies handle tax/payment for remote workers?

I'd say that if it's regular contract, you pay the tax in the country where the company resides (+ social / health tax). Freelancing is different and the pay is taxed in the country where you reside.

I imagine in many cases this would be on a freelance/contract basis and in that case it would generally be the remote worker who is responsible for paying the appropriate taxes in their country

Remote workers are usually on a contract and pay their own tax in their country.

If the company wants them to be a full employee, they have to pay tax/health based on the law of where the remote workers lives.

In the US, the company only has to withhold income for statutory employees. If this presents problems, then the work is usually let by contract.