I'm not sure which order they come, but as far as publishing dates, the first victory was in The Bottom Line, which was printed in "Strange New Worlds III". This was the more interesting of the two -- purely tactical as far as I can tell. Although whether he won or not is somewhat dubious. With the tractor beam, he slingshots the Kobayashi Maru towards the border, and then engages with (in this simulation) the Cardassians in battle. He then signals his surrender and shuts down systems. When they began boarding the ship:
Nog rushed to his chair and triggered "the bottom line."
"Five seconds to auto-destruct," the ship's computer announced at the lowest setting Nog and his crew had been able to manage when they'd rewired the system. Only his ears could pick it up, he hoped.
He destroys his ship with the hopes that it'll damage their ships enough to give the Maru a chance to coast across the border. But when he asks if he won, he's told by an instructor that "You're dead. You'll never know." To me, this doesn't quite qualify as "beating" the simulation, but it does seem like he'd get a passing grade.
The second victory appears in the short story Best Tools Available, which appears in "Strange New Worlds VI". Paul D. Waite isn't far off -- Nog makes the Romulan crew an offer:
"Ferengi," the Romulan officer demanded, "you are in violation of intergalactic treaties and we are perfectly within our right to destroy..."
"Name your price!" Nog demanded. The crew looked at him in stunned silence. Surely he did not say what they thought he had just said.
He argued with the (simulated) Romulan for a while, and then the transmission appeared to begin breaking up, and then the simulator halted entirely. Nog broke the Kobayashi Maru by trying to deal with it in a way it wasn't programmed to handle: the Ferengi way.
Actually, re-reading the stories, they both seem to treat this like Nog's first time taking the test, and both depend on him getting pivotal advice from Boothby. So I'm thinking they're alternate stories. Thanks to the fuzzy canonicity of printed Star Trek stories, they are both true and untrue.