> Regular people here in Poland seem to universally think along the lines of "look at our gasoline places, it's so expensive [compared to the US], most of it is taxes already, and you want to add extra tax?!".

You could suggest changing the road taxes or exempting gas from VAT at the same time as implementing a carbon tax. It would actually come out cheaper, if we can get the carbon capture price down to $100/ton or less (some estimate $60/ton is viable).