Your best bet to improve the amount of push ups you can do is to do both of them.
Do as many regular push-ups as you can, and then when you get to failure keep pushing yourself at the point of failure (don't just collapse as soon as it gets hard).
Then, when your muscles can no longer lift your entire weigh, go to push ups on your knees which are less weight and do them until you are at failure, too.
The goal to getting better at anything, particularly strength training, is to maximize the amount of time you spend tearing the muscle fibres (if you can do 8, the first 6 are useless other than getting you to the point of 7-8 when you are struggling).
Don't forget other things like nurtition and rest, either. After you do them, max out on protein consumption, and if you do a few sets in a day, take a few days off to allow the torn muscles to rebuild using that protein. If you do push ups all day every day you will see a slight increase but your muscles will never fully recover and your gains in the long run will be less.
