Summary: go with a buck regulator which saves power and space.
If linear regulator is still a choice, due to the huge voltage difference between input and output (12-3.3 = 8.7 V) and the current through linear regulator ( 350 mA) you would see a power dissipation of about 8.7 * 0.35 = more than 4 W!!. This huge power is dissipated as heat.
Adding a big heatsink, will help the regulator to live the huge heat dissipation. Also. Chose the linear with thermal packaging which has got good (lesser thermal resistance) thermal characteristics.
Another option is to bring down the voltage to 5 V or 4.5 V using switching regulator. Placing the linear after the switching regulator now will be dissipating lesser heat because it has to drop lesser voltage across it.
Relevant application note from TI : Google "SLVA 462"
Understanding Thermal Dissipation and Design of a Heatsink