Just figured it out for Outlook 2010. Here's what you do:
1. Go into your contacts and click "View" at the top
2. Click on "View Settings"
3. Click on "Columns"
4. On the left side, scroll down to "Notes" and click on it, turning it blue
5. In the middle, click on the "Add" button. That will add it to the bottom of the list on the right.
6. If you don't want it on the bottom, use the "Move Up" button on the bottom of the right-hand pane to move it into the placement you want.
7. When everything is the way you want it, click okay and voila!
This works to add (or remove) any other column you want. For example, only the mailing address shows by default. If you want both home and office, remove "mailing" and add the others. This is actually more flexible than it used to be, but harder to find.
For reasons I don't understand, though, a "Notes" section will appear for some contacts that don't have notes and I can't figure out how to get that to disappear. But it's a small price to pay to get all the notes information to print. If someone has a solution to that, I'd be grateful.