For online gaming it's not so much the actual throughput than the latency. Typically online games do not require much bandwidth - a 256 kbps speed is far more than enough (but you'll want at least 2 Mb/s download and 256 Mb/s upload for browsing and downloading stuff so don't limit yourself). What is really important is latency, which is the time taken for you and the server to communicate. Depending on the game, your latency may or may not be sufficient, for instance for online first person shooters you want :
1-80 : good gameplay
81-150 : decent gameplay
150+ : pretty frustrating as people seem to kill you instantly, around a corner, etc ...
But it also depends on the actual game and its netcode, for instance Battlefield 2 netcode is absolutely horrible and does no high-latency corrections, which essentially means "first to server gets the kill" - newer games should compensate for each player's individual latency to improve fairness.
Latency is also physically limited by the speed of light in a copper wire (which is the most used medium, optical fibre being on average not used that much), which is about 160000 km/s - that is, if the distance between you and the server is X kilometres the absolute best latency you can expect is (X / 160000) * 2 seconds, so about (X / 160) * 2 milliseconds. The "* 2" comes from the fact that the server needs to respond (most of the time), so we need double time for that to happen.
Which essentially means that if you want a latency of at most, say, 100 milliseconds, you need to be at at most 8000 km from the server. Which is probably easy if you live in north america, but is harder if you live in australia for instance.
Of course this is theoretical and your mileage may vary depending on if you're playing overseas or if your whole state is frikkin wired with optical fiber, so in conclusion make sure that :
- you have sufficient throughput, that should be ok if you're not on dialup
- your ISP provides low-latency ("low-ping") internet access
- you choose a server that is close to you, say in your state for best results if you're in the USA
Note that if you're in very remote locations like australia, new zealand, etc ... you won't be happy at all with your latency (about 200-300 ms) on most european/american servers, so you'll have to find an oceanic server - just a word of warning for whoever it concerns.