Legacy software and code coverage

According to Michael Feathers, software is considered legacy if it does not have automated tests supporting it. And, not surprisingly, there are (too) many legacy applications out there. And that raises a couple of questions: how do you change legacy code? yes, but how do you change it without feeling the urge to update your cv? Mr Feathers gives a lot of hints on changing code and dependencies-breaking techniques, presenting you with different problems and possible (and tested, of cours) approaches.
At the moment I am working on an "inherited" old (and, yes, legacy of course) application for which I'll have to check several chapters of Feather's book: I can't get this class into a test harness, I can't run this method in a test harness, dependencies on libraries are killing me, my application is all API calls, my project is not object oriented how do I make safe changes, this class is too big and I don't want it to get any bigger, I'm changin the same code all over the place, I need to change a monster method and I can't write tests for it, how do I know that I'm not breaking anything, and so on and so forth.
So... where to start from? The answer is quite simple: I have to write tests. OK, that was easy. Which tests should I write first? short question, long answer. Long story short: check the book for that. But how do I know what's covered and what's not? Thanks to Fabrizio I've discovered Cobertura, a test coverage tool which instruments the bytecode of your classes and produces reports about, well you guessed, test coverage; you can see a sample report here. Fabrizio shows how to integrate Cobertura in NetBeans, which happens to be my favorite IDE. I did it and... well... I have quite a lot of work ahead, but at least I have a new tool.