You have two problems right now that are separate from each other.
1) Button bounce
2) Improper button wiring
First, you need to introduce a delay into your interrupt function so that it won't keep registering each rise and fall of the bounce as a separate button press. Use "delayMicroseconds()" because apparently you can't use regular "delay()" inside interrupts. Id suggest a 20,000 microsecond delay.
Second, you need to put a pull down resistor onto the digital pin that you are sampling.
The problem you are having is that the pin is in input mode and thus at high impedance (very high resistance) and thus has a tenancy to "float". If you put a voltage to it, it charges up like a capacitor and since the pin itself has very high resistance to ground, it takes a while for the charge to dissipate to the point where the Arduino will register a LOW again. A 10k resistor from the pin to ground will force the "capacitor" to discharge quickly after current from the button has stopped flowing.
Finally, the Arduino is pretty quick at it's read/write operations (I'm a mechanical engineer, ALL electronics happen "quickly" in comparison to mechanical systems, so it's relative I guess). Here's a link to some test results.
TL;DR verson:
What these values tell me, is that we can do about:
10 analog 10-bit readings per millisecond with analogRead()
128 pwm settings per millisecond with analogWrite()
220 pin reads per millisecond with digitalRead()
224 pin writes per millisecond with digitalWrite()
1056 pin reads per millisecond with direct port reads
1059 pin writes per millisecond with direct port writes
Debouncing is something you must be familiar with when using buttons. When a contact closes, it does not just close, but bounces back a few times until it finally settles in its closed position.
Depending on how fast your sampling code is, the code can count many button presses, although you only moved your finger once. There are a number of debouncing strategies around. Search www.avrfreaks.net for debouncing and you will find plenty of posts. Most of the recent threads contain a link to some pretty good old examples/strategies which you can use.
This might not be the only problem with your code - but we can only know that when we've seen the code. Post it here or on avrfreaks and we might be able to help you.
Best Answer
I would highly recommend hooking a scope (hopefully you have one or can get your hands on one to use) up to your switch. I have seen a student's project that had a bounce on their switch that went from 5v down to -5v up to 4v down to -3v then up to 2v then back down to 0v. When we looked at the current draw on a scope there were some a very very large spike.
In his particular case it was very very much needed for him to debounce his switch in hardware.
However, on the other hand, I have seen switches that have a much smaller effect that could easily just be removed in software.
You do need to weigh your options though. If you have a very complex amount of firmware, adding the overhead on both you as a programmer and the cpu usage may not be worth it and you would be better off to just add a little bit of hardware. Now on the other hand, if you are trying to get costs and size down, you will want to remove as much hardware as possible and do it all in firmware if you can.