You need to at least implement attempt counting at a per-account and per-IP level, so that password cracking is blocked regardless of whether it's one account and lots of passwords, or lots of accounts and a few common passwords.
The best way to do the count is to log the attempts to a database table, then compute the count at runtime using a query. You could use a set of queries like this to compute the counts:
// get the last successful login time.
// if this returns no rows, default it to 2000-01-01 00:00:00 or similar
SELECT TOP(1) attempt_time AS last_success_time
FROM login_attempts
WHERE success = 0
SELECT MAX(tmp.attempt_count) AS attempt_count // we want the highest count
FROM (
SELECT COUNT(*) AS attempt_count
FROM login_attempts
WHERE
attempt_time > $last_success_time // only count from the last successful login
and success = 0
and ip_address = $ip; // count by IP
UNION
SELECT COUNT(*) AS attempt_count
FROM login_attempts
WHERE
attempt_time > $last_success_time // only count from the last successful login
and success = 0
and user_id = $uid; // count by user ID
) tmp;
Another thing to watch out for is proxies. Most people worry about them and attempt to use headers such as X-Forwarded-For to block source IPs. The problem with this is that X-Forwarded-For can be set by an attacker and used to get any IP address banned, simply by failing to log in. As such, you should check for existing bans based on X-Forwarded-For and the source IP, but never set new bans based on the header. This means that users attempting to evade bans by using a proxy will be caught if the proxy supplies X-Forwarded-For, but attackers can't spoof via it. It also has the side-effect of banning proxies that are used for attacks, which is a nice bonus.