Once Ur-Shak tells you about the ULU-MULU, teleport back to Xardas and report to him; then teleport back to Saturas. Riordan is in the room with him and will tell you to go speak with Gorn around the bend leading towards the Free Mine. Talk to Gorn and learn that they've been waiting for you to lead the strike to recapture the Free Mine; agree to help, and he tells you that Wolf wants to talk with you before you go. Wolf says that he's discovered a new way to create armor using the shell plates of the minecrawlers in the Free Mine. Whether you agree or disagree with him has no bearing on the over-all quest - save the Free Mine - but you may want to take him up on his offer for the Minecrawler's Plate Armor he's going to make. It just means, at worst, you'll be fighting half a dozen more minecrawlers.
Return to Gorn and you both will set out on your own. After fighting some Razors in the clearing before the mine, Gorn will give you a key to the storage shed and tell you to clear out the front while he watches your back. The Free Mine exterior is strewn with the corpses of its entire population. Feel free to loot the corpses; a 96 damage two-handed axe can be gotten from the corpse of Okyl. Down at the base of the path, near the gate to the mine, is Jackal and two Guards. You must defeat them to proceed (remember to actually kill them using melee, rather than just knock them out; they won't stop fighting, even after you beat them up and steal their weapons). Jackal has a Heavy Crossbow worth taking. Once they're killed, saved the game, go over to the supply shed and use the winch inside to open the mine gates. If the winch is jammed (glitch), reload and try it again. If you still can't use the winch, you will have to Marvin Mode your way past the mine gate.
Once you enter the mine, you'll be in for a real fight. Most of the guards have Light Crossbows and will snipe at you from a distance, rather than run up and engage you in melee. Personally, I recommend handling the entire Free Mine in turn - use a bow or crossbow yourself. The benefits of fighting from a distance is that, at point-blank range, crossbows are almost unerringly accurate and lethal, and any Guard who has already drawn a crossbow will not try to charge at you (so you can safely stay out of their range while you fight other enemies). Advancing slowly is the preferred method.
For the purposes of this quest, you have to kill everyone in the Free Mine except the minecrawlers and the Orc slave (PLEASE don't kill the Orc slave!). That means: Guards, Diggers, and Shadows. If you find a strange potion while adventuring, don't drink it. If you're doing Wolf's subquest, grab plates from the mincrawlers as you kill them.
After a while, Gorn may bug out and act like you've been threatening him, or like you've killed someone from the Free Mine. This will have no impact on the rest of the quest, save that he will suddenly attack you and knock you unconscious. This is a dangerous position to be in because, although the Guards with melee weapons will stop charging at you, the Guards with crossbows will still fire at you if they can, which will kill you. Erring on the side of caution, proceed through the mine yourself, telling Gorn to wait by the entrance right after clearing the first room.
After you clear the second chamber, the mine leads off to the right and down two ladders. Unfortunately, the Powers That Be decided to place two Guards with crossbows around the base of the ladders. While you descend, you'll get the wonderful pleasure of being sniped from below almost as soon as you start on the second ladder and, if you're hit, you'll fall to the ground below. AND, if that fall doesn't kill you, you'll die as the Guards continue to rain down bolts upon your helpless, paralyzed body. A work-around is available: from the first chamber, go down and kill the two minecrawlers in their small connecting cave. Proceed right, through the cave, to the gap. Although the jump may prove difficult, you can leap across the gap and land on a ledge with a bunch of items. Walk forward through the wood and off the end of the ledge ... to end up standing right next to your Orc slave! Proceed to butcher the rest of the Guards.
You'll find the Orc slave Tarrok having had fled onto this platform during the invasion of the Old Mine's Guards, but he'll tell you that a minecrawler poisoned him while he was getting to this safe spot (you may be able to know what he's talking about, since he uses the Orcish word for minecrawler, but you have to ask what his word means anyway). Tell Tarrok you'll find his Medicine, the aforementioned "strange potion." It's on the other side of the same room, under the wooden walkway, hidden amongst some mushrooms. Return to him with it and he'll agree to make an ULU-MULU for you if you bring him its four components. Ask what each of the components means in English and you'll learn what you need to acquire (see below). These are all new components that cannot be harvested from bodies before talking to Tarrok. After you find all the items, return to Tarrok and he'll fashion the ULU-MULU for you. The ULU-MULU is a weapon-type item that must be wielded, not just equipped, for it to work.
To complete the Free Mine part of the quest, meanwhile, just exit the mine after having killed everyone from the Old Camp and talk to Gorn outside. Go back to the New Camp and ask Lee about what he thinks of the mine to earn your experience. If you're performing Wolf's quest, return to him to give him all the minecrawler shells you've found. If you have any left over, you can sell the remaining shells.
Teeth of a Swampshark
Teleport to the Swamp Camp and head towards the uninhabited parts of the swamp (if you've done The Swampweed Harvest you know where to go.
Tongue of a Fire Lizard
Teleport to Xardas' tower and then head down to the beach. The Fire Lizards can easily kill you, so it's best to pick one off and then either shoot it with something or else attack it rapidly with your mêlée weapon.
Horn of a Shadowbeast
Shadowbeasts are tough. An easy way to find one is by exploring the forest between the Old Camp and the Swamp Camp. There were also some Shadowbeast horns in Gomez's chests if you managed to rob them.
Tusks of a Troll
Head to where you found the Focus in the Troll Canyon and a Troll will be waiting for you. Defeat it in much the same way as before.
Once you have all the ingredients return to Tarrok and give him the items. He then crafts an ULU-MULU. Bear it with honour.