No need to complete a factory reset for a deleted shortcut.
Avenue 1 Open your application drawer and scroll down to the Messaging icon. Long press it and the screen will switch to one of your main home screens. Drag the icon to the location you want it at.
Avenue 2 In the spot where the icon was, long press to get the ADD menu. Select application and scroll through to the messaging application and select it. The icon will be added to the screen in the location where you pressed.
If the messaging application was in docked icons at the bottom, READ the online manual. You can find it on Samsung's website and AT&T's website.