This is one of the real annoying things. Why can Outlook / ActiveSync / PocketPC not handle categories for notes just the same way as for calendar and contact entries?
At least, I found some good info hereĀ
Using Outlook categories to work with your data easier
Pocket PC Thoughts - Daily News, Views, Rants and Raves.