It sounds like you're just getting started into the world of shocks, so it might be worth taking this back to the shop where you bought it and asking them to help you set it up. This kind of thing is a lot easier in show-n-tell mode than reading over the interwebs. However, I'll give it a shot.
It sounds like you need to increase the amount of air that you have in the chamber. The easiest way to set this is to set the "sag": the amount that the fork compresses when you're just sitting on it. Unfortunately, this is hard to do yourself. However, if you can get someone to help you, have them measure the amount of stanchion tube (the shiny uppers on the fork) showing when you are just sitting comfortably on the bike (both feet on, and leaning against a wall just enough to keep your balance). You want your sag to be about 15%, but for starters here you can aim for 10-15mm of sag, or 65-70mm showing when you're on the bike.
After you've done this put a zip tie around one stanchion. This will allow you to keep track of the amount of travel that you're using on the trail. As a general rule, you want to occasionally use all of the travel, but not on every hit: I usually like to see that I get all the travel once a ride, assuming it's of decent length and on relatively rough trails. You can play with this later, too, adjusting how stiff you want the fork to be: I change things based on the trail, how much gear I'm carrying, and how fat I am.
You also have a rebound adjustment on this bike: this know on the bottom of one of the leg with a turtle and a hare on it (I believe, graphics can change) adjusts how fast the fork returns to its original position after its been compressed. This is a great feature that will really help you tune your fork, but for now you can just set it at about "medium" to a little "fast" (count the clicks between the two positions). Don't worry about this too much until you're a little more comfortable on the bike, but trust me that it can come in handy.
Finally, when you lock the fork out (the knob on top of the right leg), you should still get a little bit of play in it. This isn't a bad thing -- few forks now have a "static" lock out -- and shouldn't bother you unless you do lots of road riding. If so I think it's internally adjustable on this fork, though you'll need to ask your mechanic about that.
First things first, though: get a good shock pump, a friend with an eye for measurement, and set the sag. I think that will stiffen things up quite a bit.
Good luck!
