I accidentally deleted the message App on my iPhone. How do I retrieve it?

You cannot delete the native iOS Messages app. Do a search for it, you may have accidentally moved it to another home screen, or folder. IF it is in a folder, when you search, it will identify the folder name. The only other possibility is if you set a restriction for it, Settings>General>Restrictions.