I use Shorewall to configure my iptables rules, with a default policy to DROP everything, and a single rule to ACCEPT SSH connections (well, plus rules/policies to permit outgoing traffic, of course); the effect is pretty much identical to what @MadHatter has posted, but I find Shorewall to be a whole heckuva lot easier to configure and use than direct iptables rules. (Shorewall is a configuration layer on top of iptables, using a series of easier-to-understand configuration files to employ complex firewall setups; it is not itself a firewall.)
Next, set up your SSH server to only allow key-based authentication, as suggested by just about everyone so far -- that should tell you how good an idea it is!
And to satisfy your requirement to block brute-force attempts, I strongly recommend Fail2ban, which can be configured to set how many failed attempts to block on, how long to ban the offending IP, and it can even monitor itself to effect a longer ban on persistent attackers not deterred by the first level of response (see the HOWTO on the Fail2ban site "Fail2ban monitoring Fail2ban"). You can even setup e-mail notifications about Fail2ban's responses: I set this piece up last night, and by this morning it had already banned a would-be Chinese hacker (based on the whois of the IP, anyway).