As for the Mag, they are rather commonly found in Mines normal boxes as far as I know. I have at least 12 of them. They operate like normal mags that a character starts with.
As for the Enemy Parts, you basically kill a butt load of whatever monster type you want and they will eventually drop a red box with the item corresponding to them.
To give you an idea of the frequency, I'm on Hard Mines now, and have found:
DelSaber's Arm (the sword one) - Normal Ruins
Gobooma's Arm - Hard Forest
Booma's Arm - Hard Forest
Grass Assasin's Arms - Hard Caves
I'm desparately trying to find a Rappy Wing, Hildebear's Cane, and Talis from De Rol Le now. I completed Fake in Yellow and Forest of Sorrow, but I've found a good mix of rappies, gigoboomas, hildebears, and what not in Gran Squall.
Hope that helps