The simple solution is to get a battery pack from RadioShack that will hold 2 AA batteries with red and black wires(#270-408 will work). To add the power pack to the setup,  locate where power line from the controllers meets the power line from the computer. If you used diodes, then the best point to do this is where the diodes come together to supply power for the controller. Cut the power wire at this point. Attach the black wire (negative) to the  diode side, and the red wire to the controller side. The diagram may explain this more clearly.
 

If you also want to use SNES controllers or other controllers which do not need the battery power, you can add a switch to activate or deactivate the pack. I've successfully connected a 3/32" jack to the interface and a 3/32" plug to the battery pack. If you connect it properly, when the plug is inserted, the interface will draw power from the batteries, but when the plug is not inserted, the interface only uses power from the computer.

Gameport/Joystick Port Solution

Another source of power from the controllers is right under your nose...in most cases. If you have a free joystick port, then you can easily build an adapter cable that runs from the interface to the gameport. It supplies a steady 5V current. If you are going to use this method, I suggest that you should not draw power from the parallel port because its unnecessary. Simply put, all you have to do for this solution is connect the power wire (normally coming from the parallel port pins 4-9) to gameport pin 1 and connect the ground wire (that usually connects to parallel port pin 18) to gameport pin 4. You will STILL NEED to connect the interface to the parallel port too. This gameport adapter is ONLY to steal power for the NES controllers from the gameport and the data must still go through the parallel port.

If you want to use a normal joystick on the parallel port, you COULD build the gameport power adapter to be a pass-thru device, but that would probably be a pain. I suggest simply buying a joystick cable splitter and that should work great.