I think I can shed some light on this for you, daz.
Your controller is indeed a 36v 16amp brushless controller. Now, electrically, that's a peak power of 576w, and the 250w rating is purely cosmetic. I highly doubt that you're using any more than half of that current with your current setup. At that mind-numbing speed of 25kph, you'll be using only 150watts (at the wheel), or approximately 5 amps.
Now, volts give you speed, amps give you thrust. That thrust is useful for climbing hills, accelerating, and (only at high speeds) fighting really nasty wind resistance. If you want more speed, you need more voltage. If you replace your current controller with a 36v "500w" or "800w" controller, the only difference will be the controller's maximum current limit. Since your controller is able to supply more current than you can use at 36v, you will see exactly
zero speed increase on flat ground. None.
The easiest thing to do is add more voltage. A 12v 10ah battery, preferably of the same chemistry as your 36v10ah battery, is the simplest solution. And the wiring is really, really simple.
See this plug? It connects your battery to the controller; the red wire is positive (+36v) and the black wire is neutral (Ground). What you want to do, when you have your second 12v battery is splice it in there. Disconnect the red wire. Connect the red wire from your main (36v) battery to the black wire of your small (12v) battery. Then connect the red wire of the small (12v) battery to the red wire on the controller. That sort of connection puts the batteries in series, meaning that their voltages add. If you measure the new arrangement with a voltmeter (which you should before connecting it to the controller), if you have it right it will read around 48v, or the sum of the two batteries' voltages.
Now, your controller may or may not handle that voltage. Let me explain about the different controller voltages: not counting the LVC (I'll get to that later), a higher voltage controller can almost always be run on a lower voltage battery. Many 72v controllers will work with batteries as low as 20v. The other way, though, is a little riskier. If you use a higher voltage battery with a lower voltage controller, it may destroy the controller. All controllers have to have some headroom (most "36v" batteries will be at least 40v hot off the charger, so the controller has to withstand 40v), but some more than others. It all depends on the components used inside the controller. In many cases, a "36v" controller can be used with a 48v battery (several manufacturers use almost exactly the same design and components for both their 36v and 48v controllers, since it's easier to produce them that way). I give it a 75% chance that your controller is fine as long as you don't go over 60v. If you are willing to open the controller and take some real close up pictures of its guts, we can say with much more certainty.
If your controller can't handle 48v, you'll know pretty quickly. You might hear a "pop" from inside it, smoke might come out, and (obviously) it won't work when you turn the throttle, and it'll happen within a few seconds of connecting it to the 48v battery and giving it some throttle. If it dies, you'll need to buy a new controller; thankfully they aren't very expensive nowadays. You of course want a 48v controller, and pretty much any power rating will be fine. 20a and 30a ones are common, most likely labeled "750w"
If an upgrade to 48v does work, given that you can do 25kph at 36v, you can expect to be able to do 33kph at 48v. At that speed, it'll feel like a different beast, especially how much more wind you feel rushing by. It's exhilarating. You''ll also notice that you can accelerate faster, which helps give the bike a real sensation of "power".
So, hope that clarified things for you. Any questions?
