Good to know about the heatsink conductingYou must use a heat sink with the LM317 when dealing with that kind of power dissipation.
Keep in mind that the heat sink tab is connected to Vout, so it's "live" - you must either use an electrically insulating heat sink mount kit or must ensure that the sink itself doesn't contact anything.
LM317's are great for quick and simple solutions.
But if you want to get efficient, you'll need to start looking at synchronous buck converters. It's not a simple topic, but it's far more efficient than the linear regulator route.
PWM is a possibility, but not plain PWM when you're running close to peak currents. The PWM input to the LED(s) needs to be fed through an appropriately sized inductor (load current vs frequency, just to keep it simple) to keep the current relatively constant.
Originally I looked at this http://www.st.com/stonline/products/literature/ds/13415/stcs1.pdf
but I had trouble finding the appropriate resistors. In this case I would need a 0.286 Ohm resistor for .350A. The closest I found was a 0.220 Ohm, which would be close to .5A.
The second issue is this is a power soic-8 chip and it's not clear to me how I would attach this to a breadboard or protoboard.
I also looked at the buckpuck but it's just too pricey for an RGB since I would need 3.
I'm currently using a FET, hooked up to my Arduino and seems to be dimming quite well.