Do you refactor your SQL first? Your architecture? or your code base? Do you change languages? Do you throw everything away and start from scratch? [Not refactoring]
I'm adding unit testing to a large, legacy spaghetti codebase.
My approach is, when asked to solve a problem, I try to create a new wrapper around the part of the code-base which is relevant to my current task. This new wrapper is developed using TTD (writing the test first). Some of the time calling into the non-unit tested legacy code. At other times I make a new copy of an existing module and start to do serious violence to it. Sometimes I rewrite functionality from scratch.
But as I'm keeping it fairly well tested I feel pretty in control.
What I find with this code-base, which has been developed with far too much copy and pasting, is that once I get an understanding a particular part, and extract some functions from it (which are done test-first) ... these functions often turn out to be usable in many other places and so the rate of replacing the legacy code with my own, unit tested libraries increases.
I don't (and have no authority to) try to rewrite or add tests to parts of the code that are not touched by my current problem (usually a bug I'm trying to fix) but I do have a fairly aggressive proactive stance on anything that is touched and might be relevant.
Update : Penguinix asked : "What languages do you work in? Is there a specific Testing Harness you recommend?"
Right now I'm working in ... er ... Mumps! But the same principle works anywhere.
Something that transformed my understanding of UT was MinUnit : http://www.jera.com/techinfo/jtns/jtn002.html
When I saw MinUnit, that was kind of a "zen" moment of enlightenment for me. It stripped away the misunderstandings I had about unit testing being something complicated requiring sophisticated OO frameworks etc. I understood that UT was just about writing a bunch of tests. The "harness" you can write yourself, in about 3 minutes, in any language you like. Just get on and do it.