Like the description says you need to ride on each of the different types of animals. Here is the types with where I first encountered them:
Donkey: Port Royal (Story Mode) - needed to complete the mission. He's right at the beginning of the level. Feed him a carrot from the bowl behind him and you're good to go.
Crab: Port Royal (Free Play) - In a cage under water near the final dock you go onto to finish the mission. You need a character capable of walking on the bottom without a barrel to free it. You may then need to slap it around a bit before you can ride it.
Horse: Tortuga (Story Mode) - The horse in pulling a cart that you will have to move to get towards Mr Gibbs, so you will have to ride this horse to complete the mission. You need to put the wheels on the cart and feed him an apple before you can do this. One wheel is leaning against the wall behind him and the other is by the well. The apple is also by the well and you can use Jack's compass to find it if you're having trouble.
Pig: Tortuga (Either) - You don't have to ride this to complete the mission but the pig is in the same area as the horse. Just hit him a bit if you can't ride him right away and take him for a little bit of fun.
Sea Turtle: Smugglers Den (Free Play) - After the sun rises again, you'll go back down into the cave. Redirect the ligth until you've blown up the dynamite on the wall that you hit by redirecting the laser using the reflector with the blue/green pusher. Use the pieces to build a bridge across and continue left until you see some silver blocks on the wall. Blow them up with a grenade or Marty's big gun and go up the ladder. Move left towards the beach and you'll see 2 ice blocks. The turtles are encased in this ice so you'll need a character who can sing (Phillip or one of the mermaids) to break them out. While you're riding them, you might as well take them around through the little course that's right in front of them for a minitkit.
Snail: The Dutchman's Secret (Free Play) - Once you get inside the ship, go down a level and head to the left. Use a strongman character (Davy Jones, Blackbeard, etc) on the orange bar and jump down. On the back wall right where you jump down is one of the green passageway things. Use a member of Davy Jones' crew to go through and come forward and put a sword into the lever device. Have your other character do the same with the device on the other side. This will lower some spikes that were skewering some Lego pieces that you can now build to make your snail.
Giant Crab: Isla Cruces (Free Play) - NOT NEEDED for the achievement, this seems to count as a crab because I got the achievement before I rode this. This is just for fun. This is not the first Giant crab you have to fight to progress, after the water wheel bit you'll be back on the beach under attack by Davy Jones' crew. Go to the right and look for the Davy Jones' crew passage in the water (the one closest to the screen). Go through and retrieve the golden crank and come back and back to the left up the beach (near the quicksand pit) and use it to extend a bridge. Use Jack's compass to search for crab and then build the pieces. This one won't let you ride it but it will circle some big claws buried in the sand. Use a female character to then swing along the bars by the tree line to get to the chain and drop some pieces you can use too build a second crab. The big one will come out and you can ride it. It will put up a little fight (scripted) and then you can steer it, including back over the quicksand pit to help in your fight against Davy Jones' men.
Goat: Davy Jones' Locker (Story) - You need the goat to progress. Use Jack's compass (only the real Jack has one none of the imaginary ones do), to find the purple flower. Once you do break it apart and bring it over to the back of the Black Pearl and give it to the goat. You'll use it to pull the strongman bar in story mode to pull the back of the ship out of the ground once you've put the tracks and wheels on.
Spider: Fountain of Youth (Free Play) - Once you get into the caves where you have to raise the 3 lantern like objects to melt the ice, head down and keep going past the lantern that is on a chain that you need a woman to jump up to grab. Down at the end of the cave you should see a forgable object on the ground next to a large spider web. Use a blacksmith character to build a bellows and jump on it a few times to blow all the pieces out of the web. Put them together and enjoy your new spider mount. Several other spiders will come out from behind some nearby skulls on the wall. Kill them all for a minikit.