Depends on a lot of factors, but I usually like to start off at 1500 watts as my starting point for a go kart build with final drive ratios of 6:1 for this power level. Good quality motors at these power ranges tend to be a bit expensive, but if you look at the surplus sites, then you can get some decent quality motors at surplus prices.
Like just recently I bought one of these motors:
http://www.surpluscenter.com/Electrical/DC-Motors/DC-Motors-Face-Mount/2-5-HP-2000-RPM-36-VDC-MOTOR-IMPERIAL-ELECTRIC-P66SR274-10-2357.axd that are rated for about 1800 watts at 2000 RPM with 36 volts applied with current draw of 65 amps at full load, and the price is very low compared to if you bought new stock of this motor.
Next, you need to decide on motor controller that is compatible with motor type you use. In this case it is a DC brushed motor, so we need a controller for this type of motor. A good choice is the AXE4834 controller that works up to 48 volts input with current draws up to 300 amps. This controller can be programmed to limit current, speed, and accel and decel profiles.
The final step is getting some good batteries. Use sealed lead acid batteries only. Never use car batteries. Good choices are those glass mat batteries such as the Optima Yellow tops or Odyssey extreme batteries. There is also places that sell batteries out of hybrid cars at deep discounts that will work perfectly too.
I assume you already built gas go karts, so should already know all the other details that I did not cover.