How do you approach refactoring an ugly procedure/query?
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.