Converting 12-14 car battery voltage to 9v
Linear voltage regulators are usually for low power applications. It will be very hard to find one that suits your problem.

I would suggest you look for a DC/DC converter(buck-converter, stepdown-converter). There are some pre-made kits out there that you can use. (I can't give you any link because I don't know where you live, but eBay, Amazon or Aliexpress will do the trick.)

These converters also operate a lot more efficiently than linear voltage regulators and are nowadays affordable to buy (10-15$ or euro).

In the unlikely case that you can't get hold of one, you can build a step-down converter yourself. The schematic is simple enough.

*** It's propably too early in the morning^^, so I made a foolish mistake, the LM2596 is of course already a DC/DC converter (was thinking of LM7809).

I looked at its specs right now, and it said 3 A max. You say your dehumidifier takes about three amps, so you would use your converter at maximum rating all the time, which is usually bad. 

For the best result you should find a similar one with 4.5 A max or something like that.

Heatsink should work too, but in the end it doesn't change the fact that you are constantly pushing the converter to its max range.