That's strange, have you deleted it off your home screens or in your favourites tray? You shouldn't be able to delete the Samsung Messages app so it should still be in the Apps section of your phone.
- If you want it on your home page, you just need to click the application and it should then show you the home page and allow you to place it where you need it.
- If you want it in the favourites tray (the icons at the bottom of the home screen), you can drag it into the section if there is space (you can choose 4 apps to sit here).
