I'm assuming you're using the TouchWiz launcher?
If so, go to Applications and click the little silver cog symbol in the upper left hand corner. Then you can locate the Messaging app, press and hold it, and procede to drag it to the bar at the bottom. You could also switch out any of the three left apps in the bar, if you liked. Once you've arranged things the way you like, tap Menu > Save to save it that way. (Or you can hit the Back button, or the Home button.)