How do you approach refactoring an ugly procedure/query? I've inherited a database which contains several procedures which are 1000-1500 lines long, with complex nested sub-selects going up to 7 or 8 levels deep in places. I desperately need to refactor them for my own sanity, but how can I begin to do this with any level of confidence that they still work the same?

I would write unit tests if this were .Net - do you recommend a similar approach?
Yes, create unit tests.  This is really the only way to ensure that a modified version meets the same requirements as the original.

To refactor the procedures look for any repeating patterns of code that could be extracted into separate procedures or nested procedures.  If the procedures are still too long break parts of it into separate procedures that each complete one task.  As you break off new procedures you should add unit tests for it.  

Seven or eight levels of sub-selects does sound excessive, but you may find that some or even most of these are necessary to produce the data required.  I would focus on the procedure initially and then tackle the SQL.

To do unit testing in Oracle, the foremost commercial product for testing is Quest's Code Tester.  Oracle has Unit Testing built into it's free SQL Developer product.  The question Unit testing for PL/SQL on StackOverflow has some other options or you can just write your own tests.