Gulliver can sometimes be found lying on the beach somewhere on your island. Keep talking to him until he wakes up, then find his communicator parts.
Wake Gulliver Up
When you find Gulliver, keep talking to him until he wakes up. It might take a while.
Find Gulliver's Communicator Parts
Gulliver's communicator parts can be found buried under the sand of your beaches. Look for small holes that open up in the sand and spit water out. Dig where you see the holes, and you might find a communicator part. (You might find a manila clam instead, which you can use to make fish bait.)
Give Gulliver the Parts
After you have found the five communicator parts, talk to Gulliver to give them to him. The next day, he will mail you a souvenir from around the world.
After you get a wet suit, you might sometimes find Gullivarrr on your beach. Talk to him until he wakes up. He will ask you to find his communicator in the ocean. Wear a wet suit, swim in the ocean, and look for bubbles, and catch them just like you would catch deep sea creatures. Keep doing this until you find Gullivarrr's communicator. Give it to him, and he will mail you a special item the next day.
Gullivarrr can appear the same week as Gulliver, but they can't both appear on the same day.