What is the best method to add error handling in SQL 2005 stored procs?
Alex Kuznetsov has a great chapter in his book Defensive Database Programming (Chapter 8) that covers T-SQL TRY...CATCH, T-SQL transactions &amp; SET XACT_ABORT settings, and using client-side error handling. It will help you a lot in deciding which of the options makes the most sense for what you need to accomplish.

It is available for free at this site. I am in no way affiliated with the company, but I do own the hard copy version of that book.

There are a lot of little details on this subject that are explained very well by Alex.

Per Nick's request... (but not all of this is in the chapter)

In terms of scaling, you need to be brutally honest about which activities need to be in the db code and which should be in the app. Ever notice how fast-executing code tends to come back to designing for a single concern per method?

The easiest way to communicate would be custom error codes (> 50,000). It's also pretty fast. It does mean you'd have to keep the db code and app code in sync. With a custom error code, you can also return useful information in the error message string. Because you have an error code strictly for that situation, you can write a parser in the app code tailored to the error's data format. 

Also, which error conditions need retry logic in the database? If you want to retry after X seconds, then you're better off handling that in the app code so the transaction doesn't block as much. If you are only re-submitting a DML operation right away, repeating it in the SP could be more efficient. Keep in mind, though, that you'll have to possibly duplicate code or add a layer of SPs to accomplish a retry. 

Really, that's currently the biggest pain with TRY...CATCH logic in SQL Server at the moment. It can be done, but it's a bit of an oaf. Look for some improvements coming to this in SQL Server 2012, especially re-throwing system exceptions (preserving the original error number). Also, there's FORMATMESSAGE, which adds some flexibility in constructing error messages, especially for logging purposes.