First, it makes sense to understand which scenarios/attacks you're intending to handle:

• Valid user innocently mistypes the wrong password
• Valid user really forgot his password - and is willing to manually try anything he can think of
• Attacker is manually trying to guess someone else's password
• Attacker is using automated tool to brute-force a specific user's password
• Attacker is using automated tool to brute-force any possible user's password (i.e. breadth-first search)
• Attacker wants to block a specific user from accessing the site
• Attacker wants to block most users from accessing the site
• Attacker wants to block administrators from accessing the site
• Attacker wants to create a lot of manual work, or cost your org a lot in some other way.

(See? Not so simple is it...) And there are different solutions for each part of these...

• Do not reveal a list of usernames. Don't make it any easier... This includes not revealing if the username is valid or not, when refusing the login.
• Require a strong password policy - long and complex.
• Make the "forgot password" mechanism easy and noticable. (Of course, make sure that's secure too).
• Each time a login request fails, log this to the database. Make sure you write the username, IP address, time, etc.
• If numerous failed requests are received for a specific username, mark that user in the database as locked for a short time. Also encourage the user to use the "forgot password" feature, if this is in the same session.
• How many failed requests? It depends. In short, whatever makes sense for your site, the exact number is not critical.
• How long should the user be locked for? Short intervals. Mathematically, it doesn't really matter, as long as you have a strong password policy. Realistically, start with very short interval of a few minutes, then if it continues make it incrementally longer. E.g. after 5 bad tries, lock for 5 minutes; after another 3 bad tries, lock for 15; after another 2, lock for 30; etc.
• Do not lock user accounts permanently. This leads to Account DoS. And, can also cost your support personell a lot of time and money.
• Despite the previous point/s, if your site is veryveryvery sensitive, e.g. a banking app, you might want to consider locking permanently till further notice, e.g. have the customer come into his branch.
• Locks should be by username, on the database. Not by sessionId, and not in the webserver session.
• If you receive many failed requests with different usernames, but from the same IP address - implement incremental locking like above, but with wider grace and shorter intervals.
• Provide a "forgot username" feature, in addition to the forgot password.
• Administrator accounts should have shorter grace, longer intervals, and never permanently lock them out.
• In any event, when locking a user or IP, send an alert to administrators. Not for repeated locking, though - you don't want to flood the admin's inbox. But if it does continue, then elevate the alert level after a few times.
• Don't use CAPTCHA - the minimal added difficulty is trivial, in relation to the value of accessing the user's password. (There are many ways around it, CAPTCHA is fundamentally broken, regardless of implementation).
• Of course, as @rox0r stated, multi-factor authentication might be appropriate for you.
• Another alternative, is whats known as "adaptive authentication" - if the user failed the login, ask for additional information (that had been pre-registered). Depending on additional risk-factors (e.g. location, time patterns different from usual, etc), escalate the information required to successfully authenticate. For example RSA's AdaptiveAuthentication product does this.