Zidane's Ultimate Weapon: You need dead peppers to get this one with your Chocobo. After (SPOILER)you go through that island thing (man I can't remember the name) and the island is gone, the place will be right where the island used to be.
Quina's Ultimate Fork: After you catch a certain amount of frogs (I think it's 100), Quan (the head Qu guy..) will fight you, and when you win you get the Fork.

I'm pretty sure Freya's ultimate weapon is in a Chocobo Chest in the ocean. I'm probably wrong about that one.