Short version: you find very small things that you can write tests around (pulling messy logic out into testable functions, writing tested utilities that replace dirty hacks, etc.) and start building your testing framework starting with that.

Long version: Working Effectively with Legacy Code Book by Michael C. Feathers