Buffalo is on the great planes. Seagul is by the sea, I got mine in Blackwater. Mules are in mexico being ridden by some people and bucks are up north in the forrest (They have big horns and are like deer).

Bucks are most commonly found in the Tall Trees area, just roam around there and start killing all the deer like things you see and you'll get it. They are also mostly by the forest like area of Tall Trees, if you go the the snow place you won't find much. You can tell it's a buck by the really big antlers they have.
 
Buffalo are in the Great Plains area, I found it easier to load the mission "At Home with Dutch" because you ride by some buffalo and the professor points them out to you. 
 
Seagull can be found at the docks of Blackwater in the morning and afternoon, took awhile for them to spawn, but I got it there eventually. 
 
Mules...I don't think you need to kill them for the achievement, but some people ride them around in Mexico by most of the popular towns.

Are you allowed to kill them within the campaign? 
I thought t was only online?

" Are you allowed to kill them within the campaign? I thought t was only online? "

" @The_Laughing_Man: Ahh no :/ Ive been hunting animals online free roam for the past hour :( I guess I am an idiot, I was wondering why there was no buffallo in the Great Plains. Thanks for the heads up :D I dfont think I have many more to kill in the campaign anyways. "

Well, if you have killed some animals in free roam, they count as well. It's not like you have to kill all the animals in campaign to get the achievement. It's just that buffalo never show up in free roam (unless someone uses it as a stead). 
 
I killed a seagull in free roam and I never did it in campaign and I ended up getting the achievement after killing my last animal in campaign (stupid foxes, never could find them).

" Check this out  Seagull I found near black water.  And you do not need mule. Thats a domestic animal. And Buffalo can be found where its picture is on the great plains.  "

" @The_Laughing_Man: Thanks mate, Ill definatley check out that site :D Im off Red Dead at the minute but ill probably go back on within tonight. Ill check back here if I have any problems. Have you got the achievement? "

I just finished the story today and i swear i have never seen a Bighorn Sheep.

I probably and hope to be not the first one to say this, but try and use bait while in the middle of the area where to find each animal. I know this is pretty obvious, but it's the only advice I can really give.

" Yeah :/ I dont want to turn the game back on to find I have half the animals again and kill them is worrying :P I guess I have patience on my side and I have to stay up all night so it wont be that bad. Happy Buffalo hunting? :D Dont wait for the rifle just go for it. Throwing knives :P (Y) "

" @Spence_5060: Bait never helped me get the animals to come over. Hell, when I was hunting the legendary animals to finally get 100% for the game, the instructions clearly said "Use bait to lure them out", but when I did it nothing showned up, causing me to sit there and wait for the animal to arrive.  Not fun when I was waiting for the jaguar and he just pounced from a mountain and one hit killed me. "

" @The_Laughing_Man:  The jaguar is the 9th challenge in hunting and the bear, boar, and wolf are the 10th. "

" @The_Laughing_Man: God, I hated that challenge. Same thing happened to me, I never had a problem finding cougars until I got that challenge, then they never showed up. I just gave up and did some bounty missions and when I was returning to the town with one of the bounties, three cougars ran up and attacked me.  I somehow managed to kill and skin all three with the knife, but my bounty was killed in the battle. "

What system?   Also for the little challenges . If you do most of them. You will get most of the kills you need.  Right now I am going for barely legal. But I am having issues. I kill one bear and about 5 of his homies come out of no where.  "

" @The_Laughing_Man: God, I hated that challenge. Same thing happened to me, I never had a problem finding cougars until I got that challenge, then they never showed up. I just gave up and did some bounty missions and when I was returning to the town with one of the bounties, three cougars ran up and attacked me.  I somehow managed to kill and skin all three with the knife, but my bounty was killed in the battle. "

" @The_Laughing_Man: Without reloading? Yeah, that one is annoying too, but it's the final challenge in sharpshooter. I just went to one of the Mexican villages and start to shoot some people until some pulled out guns, then it was just trying to shoot the gun and not their hand in Dead Eye. "

Isn't there a late game mission requiring you to kill a Buck. Doesn't that count?