I know a lot of people have suggested fail2ban, and its a great solution that's easy to implement. The best part is it uses sendmail to mail logs to the root user about brute-force attempts. This is mainly for my curiosity.
The big thing is the ban timer on fail2ban doesn't need to be very long. The ban can be as short as 2-3 minutes and still get the message across. Once they realize they're disconnected, they'll go elsewhere. It'll slow them down enough that brute forcing ssh isn't practical anymore, usually at that point they'll move on to another host.
An easier solution is to just use public-key authentication though, there are plenty of articles out there that deal with this.
Really, just all the spam in my logs to be amusing. I had someone use a web scanner on my box, and after it was done and found nothing of interest, it made a request for /fuckingshitnonexistant.php, which of course 404'd.