I'll assume you mean for online gaming (as opposed to Steam games that just require and Internet connection for their DRM implementation).
There are (at least) two parts to this question, but most people only think of the throughput part - how fast is my connection in bps or Mbps? For online gaming, your throughput needs to be high enough so that other traffic on your connection doesn't drown out your gaming data. If you are the only one on your network, throughput really doesn't need to be as high as you think. I played online games for several years on a very solid 512Kbps down by 512Kbps up. I now have 30Mbps down by 25Mbps up, but I see little difference. Why? Because at some point, throughput is not the issue.
The second part of the equation, Latency, becomes the issue. A loose definition of latency is the time from when one computer generates a packet of data until that packet arrives at the destination computer. Assuming that your throughput is high enough that the amount of data being sent and received is not getting choked/held up, the question becomes how fast (or with how much delay) does the data you send arrive at the (online game) server and how fast is the data being sent from the server arriving at your computer? With latency measurements, the smaller the better. A 7 mSec (millisecond) latency is wonderful. So is 12, 20 or even 100 depending on the game you are playing. Typically, above 100 mSecs, you will find yourself at a disadvantage against players with a lower latency.
As in incomplete example, when you aim your weapon and pull the trigger, quite a few things have to be sent to the server: your exact location (in 3D space) on the map, the direction and velocity with which you are moving, the fact you fired, the type of weapon you fired, exactly where your weapon was pointing (also in its own 3D space) at the time you fired (and probably a lot more) is sent to the server. The server returns back to you, your health, your armor health (if such a thing exists), the location of all the other players in your field of view, their direction and velocity, whether you are being fired upon and from which direction, whether you are taking damage and how much, etc.
That sounds like a lot of data, but its not as much as you might think (although if all the players are in the same location and the server needs to report all of them to your computer, throughput can become an issue). Just as important is that the delay time from when you pull the trigger to when the server knows you have pulled the trigger and calculates what objects have been hit (i.e., barrels, players, nothing) and resulting damage to them. That is, your latency. If your opponent's latency is smaller than yours and they are firing at you while you are firing at them, their damage on you will be computed first. If there latency is significantly smaller, the server may compute that they have fired upon and killed you before your first damage on them is even computed. You die; they don't even get a scratch.
This is why satellite Internet is fine for streaming video - a large amount of data going in one direction at a nearly constant rate, but is useless for online gaming. The latency of a satellite connection is typically no less than 500 Msec - 250 mSecs for the signal to go up from one computer to the satellite and another 250 mSecs for the signal to be rebroadcast from the satellite down to the receiving computer. Your dead before you even see the other guy. Some cable connections have a similar issue. They may offer 30 Mbps down by 5 Mbps up, which sounds great, but if the cable coming into your home runs 5 miles before it gets there, the latency might be atrocious. I know someone who added 1.5 Mbps down by 256 Kbps up DSL alongside their cable connection (which was 30/5 Mbps). They used the DSL connection solely for gaming. Their throughput on DSL was 1/20th of that on cable. Their latency went from over 300 mSecs on cable to typically under 50 mSecs on DSL. Online games went from unplayable to pretty darn fun for them.
Sorry about the lecture, but people forget about latency all the time. The bottom line is probably on the order of 1.5 Mbps down by 512 Kbps up with a latency of no more than 100 mSec to the servers you want to play games on. The problem is you can get a guarantee of throughput, but not of latency. (One factor of latency is how far away the server is from you, which your ISP would not be able to predict.) If you have a neighbor who has the service you are thinking of getting, you could have them run various network tests like those at http://www.speedtest.net/ to various locations/cities and see what they are getting.