You might get better answers if you tell us which state park you’re talking about, but I’ll try to give you general advice.
How do I add them to OSM?
Since you’re new to OSM, you’ll probably want to learn how to use iD, the browser based editor built into the OSM site. IMHO it has the gentlest learning curve of OSM editing tools and is the most accessible for n00bs. If you stick around as an editor, you’ll probably eventually want to graduate to something a little more advanced, which is where JOSM comes in. JOSM is a separate Java-based app designed for editing OSM.
Do I need to upload them as GPS traces?
No, you wouldn’t need to upload any GPS traces. OSM does store GPS traces, which are useful for some things, but state parks are represented by areas. To edit a state park in OSM, what you’d wanna do is add new nodes or edit the existing nodes that make up the polygon that represents the state park’s boundaries, which will change the shape of the area in OSM.
I’d recommend checking out the Beginners’ Guide on the OSM wiki.