I'm running tomcat6, and I'm unclear if I need to set java_opts or CATALINA_OPTS?
Also, in catalina.sh there is allot of references to CATALINA_OPTS, so I'm not sure either where I should be modifying the heap size?
You can set JAVA_OPTS or CATALINA_OPTS at the top of the catalina.sh file. All the places a new value is set they ensure that it is appending to the existing values.
I prefer setting it in startup.sh instead of catalina.sh. Setting it in catalina.sh would apply to the process started by shutdown command as well.
The proper way to add custom things to Tomcat is by creating <tomcat_home>/bin/setenv.sh
(on Unix) or <tomcat_home>/bin/setenv.bat
(on Windows).
See this question as an example.